带权图 最短路径 代码自己写
?
最短路径问题
?
可能在带权图中，最常用遇到的问题就是，寻找两个点间的最短路径问题。
这个问题的解决方法可以应用在现实生活中很多情况，从印刷电路板到项目的调度都适合，但是它
比前面见到过的问题更负责一些，所以首先还是来看一个真是世界的场景，它还是发生在前面的引入的那个虚拟的国家
?
?
铁路线。
?
? ?这次我们来模拟的是铁路线而不是有线电路线了。然而，这个项目不像上一个那么浩大，这次并不是要修铁路
? ?而是铁路已经建好了。这次只是想找到从一个到另一个城市的最低费用
?
? ?旅客在两个城市间搭乘火车需要固定的费用。
? ? 图的边是有方向的，也就是有向带权的。我们要最关心的是路费的便宜了。最类问题叫做最短路径问题。这里说说的最短
? ? 并不一定只的是距离的最短，可能是费用的最少，时间的最少，效果的最好。、
?
? ? 最便宜的费用
? ? 任何两个城市间都有几条可能的路线，最短路径是这样的：
? ? ? ?对一个给定的原点和终止点，走哪条线路费用最低，带有向带权图
? ? ? ?正如前面提到的，铁路只有一个方向，所以火车在任何两个城市间只能朝一个方向进行。这相当于一个有向图，本来应该
? ? ? ?描述一个更接近现实的情况，也就是乘客可以花同样的钱在两个城市间往返。那就相当于一个无向图了。然而最短路径的问题
? ? ? ?在这两种情况下是类似的。所以为了体现多样性，我们来看这个问题在有向图中是怎样解决掉的
? ? ? ?
? ? ? ?
? Dijkstra 算法
?
? ? 为了解决最短路径问题而提出来的方法叫做Dijkstra算法，Edsger Dijkstra在1959年解决了这个问题。
? ? ? ?这个算法是的实现是基于图的连接矩阵的表示法中的。让人感到有些惊奇的是它不仅仅能够找到任意两点间的最短路径，
? ? ? 还可以找到某个指定点到其其他所有顶点的最短路径。
?
?代理人和铁路路线
?
?我们假设的要从a这个顶点开始，找到它到其他顶点的最低费用的路线。
?我们开始我们的想法了：
?
? ? 在每个城市中，站长会告诉从该站到下一个站点的费用，也就是单程的费用。但是这个站长不知道，其他站的价格了。
? ? 这里需要用到一个记事本，本子为每个城市留一列位子，并且希望每一列的最后显示从源点到其他城市的最低费用。
?
? ? 第一个代理人：在A城市
? ? ?最终，需要再每个城市放一个代理人，这个代理人的工作就是保持到其他城市的信息费用的信息的。你自己就是A的代理人
? ?A城市站长所能告诉你的是到B城市的价格还有就是D城市的费用，把这些记录叜笔记本上，如果站长不知道，那么就记无限大。
? ? ? 意味着不能从A到达表中的每一列的列头所示的城市，或者至少目前为止不知道如何到达那里。 ? ? ? ?（这个信息有用的，不要着急）
? 规则
? ?总是把本站代理人的弟弟派到下一个城市去，从源点到这个城市的最低费用。一起到B城市去，在那里成成为了代理人。当他达到那里的时候，
? ?他将问站长到下一站 C 和 D的费用 其他是无线大
?
? ? ?经过简单的计算以后，从A到B到C的费用110，所以修改了在笔记本上的条目，从A经过B到D的费用是140元
? ? ?然而刚才知道了从A到D的费用是80元，由于值关心的是从A出发到目的地的最低费用，所以忽略这条最贵的路线了。笔记本上相应的条目也不做修改了
?
? 在某个城市有代理人以后，可以确定的是这个代理人走过的路费是费用最低的路线。为什么呢？考虑现在的情况，如果有另一个线路比从A到B的直接
? 连接更便宜，它需要通过其他的城市，但是从A厨房的另一条路线到D，它已经比到B的直接费用更加贵了。加上D到B的费用，使得这条费用更加贵了
?
?
? 因此可以确定的是，从现在开始，不需要改动A到B的最低费用了，不管找到什么城市，这个费用都是不会变的。在它的旁边标注一个*号，表示在这个
? 城市有一个代理人了，并且到它的最低费用是固定的。
?
?
?
? ? ? ?
? ? ? ??/**
??
?
?
