6.3.3 最短路径算法--Dijkstra算法，Bellmanford算法，Floyd算法，Johnson 算法最短路径算法在交通地图上，两地点之间的路径通常标有长度，我们可以用加权有向来描述地图上的交通网。
加权有向图中每条路径都有一个路径权值，大小为该路径上所有边的权值之和。
本节将重点讨论顶点之间最短路径问题。
在实际问题中，路径权值还可以表示其它类型的开销，例如两地之间行程所需要的时间；两任务切换所需代价等。
本节讨论的最短路径具有方向性，问题用图的术语描述为：给定一个起始顶点s和一个结束顶点t，在图中找出从s到t的一条最短路径。
称s为路径源点，t为路径汇点。
最短路径问题可以进一步分为单源最短路径和全源最短路径。
● 单源最短路径定义为，给定起始顶点s，找出从s到图中其它各顶点的最短路径。
求解单源最短路径的算法主要是Dijkstra算法和Bellman-Ford算法，其中Dijkstra算法主要解决所有边的权为非负的单源最短路径问题，而Bellman-Ford算法可以适用于更一般的问题，图中边的权值可以为负。
● 全源最短路径定义为，找出连接图中各对顶点的最短路径。
求解全源最短路径的算法主要有Floyd算法和Johonson算法，其中Floyd算法可以检测图中的负环并可以解决不包括负环的图中的全源最短路径问题；Johonson算法同样也是解决不包含负环的图的全源最短路径问题，但是其算法效率更高。
1 基本原则最短路径算法具有最短路径的最优子结构性质，也就是两顶点之间的最短路径包括路径上其它顶点的最短路径。
具体描述为：对于给定的带权图G=(V, E)，设p=<v1, v2, …,v k>是从v1到v k的最短路径，那么对于任意i和j，1≤i≤j≤k，p ij=<v i, v i+1, …, v j>为p中顶点v i到v j的子路径，那么p ij是顶点v i到v j的最短路径。
最短路径算法都使用了松弛(relaxation)技术。
开始进行一个最短路径算法时，只知道图中边和权值。
随着处理逐渐得到各对顶点的最短路径的信息。
算法会逐渐更新这些信息，每步都会检查是否可以找到一条路径比当前给定路径更短。
这一过程通常称为“松弛”。
如图为单元最短路径算法的松弛操作。
问题为求求解顶点s到图中各顶点之间的最短路径，用d[i]表示顶点s到顶点i的最短路径的长度。
对权值为1的边(v, w)进行松弛，若当前到顶点v和w的最短路径的长度分别6和8，如图(a)，则此时d[w]<d[v]+ω(v, w)，所以对d[w]的值需要减小，并且s到顶点w的最短路径为顶点s到v的最短路径，再经过边(v, w)，如图(b)。
我们用d[i]数组表示顶点s到顶点i的最短路径的长度，用p[i]表示顶点i在最短路径中的父顶点。
可以将边松弛过程用一下代码来描述：Relax(v, w, ω(v, w))if d[w]>d[v] + ω(v, w){d[w]=d[v] + ω(v, w); p[w] = v;}2 单源最短路径单源最短路径定义为，给定起始顶点s，找出从s到图中其它各顶点的最短路径。
这里我们将得到的结果称为最短路径树(shortest path tree)，其中树根为起始顶点s。
2.1 Dijkstra算法在前面章节中讨论最小支撑树时，我们讨论了Prim算法：每次选择一条边添加到最小支撑树MST中，这条边连接当前MST中某个顶点和尚未在MST中的某个顶点，其权值最小。
采用类似的方案可以计算最短路径树SPT。
开始时将源点添加到SPT中，然后，每次增加一条边来构建SPT，所取的边总是可以给出从源点到尚未在SPT中某个定点的最短路径。
这样，顶点按照到源点的距离由小到大逐个添加到SPT中。
这种算法称为Dijkstra算法，具体的实现跟Prim类型，分为普通实现和基于最小堆的实现。
首先，我们需要明确Dijkstra算法的适用范围是权值非负的图，即解决带有非负权值的图中的单源最短路径问题。
下面对这一属性做简单分析。
给定顶点s，通过Dijkstra算法得到的最短路径树中，从根s到树中各顶点u的树路径对应着图中从顶点s到顶点u的最短路径。
归纳证明如下：假设当前所得到的子树具有这一属性，向当前子树中添加新的顶点u，满足：从顶点s 出发，经过当前SPT中的树路径，并最终到达u。
可以通过选择，使得所选择的s到u的路径比所有满足条件的路径都更短。
所以增加一个新的顶点将增加到达该顶点的一条最短路径。
如果边的权值可以为负数，那么上述证明过程将不成立，上述证明中已经假设了向当前子树中添加新的边时，路径的长度不会递减。
然而在具有负权值的边的图中，这个假设不能满足，因为所遇到的任何边都可能指向子树中的某个顶点，而且这条边可能有一个负权值，从而会使得到达该顶点的路径比树路径更短。
以下是Dijkstra算法的实现，Dijkstra算法和基于优先队列的Dijkstra算法都在SingleSourceShortestPaths类中实现，类中包括存放每个顶点到源点的最近距离D 数组和存放各个顶点的在SPT中的父节点V数组。
/** Dijkstra 算法寻找图中单源点最短路径* 输入为待寻找的图G以及源点s* @param s 起始顶点*/public void Dijkstra(int s){if(s < 0) return;int nv = G.get_nv();// 初始化for(int i = 0; i < nv; i++){D[i] = Integer.MAX_VALUE;V[i] = -2;// 0 没有添加到树中G.setMark(i, 0);}// 对起点s，父节点为-1，距离为0V[s] = -1;D[s] = 0;G.setMark(s, 1);for(Edge w = G.firstEdge(s);G.isEdge(w); w = G.nextEdge(w)){D[G.edge_v2(w)] = G.getEdgeWt(w);V[G.edge_v2(w)] = s;}/*在其余顶点中找到与当前SPT最近的顶点v，并将* 顶点的父节点和顶点v添加到SPT中。
其中图的* 权值存放在节点v中。
* 循环迭代，直至所有顶点都遍历一遍.*/while(true){/*获取与当前树距离最近的边，其终点为最近的顶点* 起点为最近顶点的父节点 */Edge E = Utilities.minNextEdge(G, V);//如果边为空，函数返回if(E == null)break;System.out.println("ad (" + E.get_v1() +", " + E.get_v2() +"),\t" + G.getEdgeWt(E));// E的终点v被访问过了int v = E.get_v2();G.setMark(v, 1);// 更新与v相连的所有边的距离（松弛过程）for(Edge w = G.firstEdge(v);G.isEdge(w); w = G.nextEdge(w)){if(D[G.edge_v2(w)] > (D[v] + G.getEdgeWt(w))){ // 更新最短距离D[G.edge_v2(w)] = D[v] + G.getEdgeWt(w);// 更新父节点V[G.edge_v2(w)] = v;System.out.println("rx (" + w.get_v1() + ", " + w.get_v2() +"),\t" + G.getEdgeWt(w));}}}// 根据V数组建立最短路径树SPTspt.addChild(s, s, new ElemItem<Double>(D[0]));spt.setRoot(s);int f = -1;// 顶点标记数组，V_idx[i] == 1表示i顶点已经在SPT中，否则不再SPT中int[] V_idx = new int[V.length];// 初始化for(int i = 0; i < V_idx.length; i++)V_idx[i] = 0;// 起始顶点s已经在SPT中V_idx[s] = 1;while(true){f = -1;for(int i = 0; i < V.length; i++){// 顶点i不在SPT中，其父顶点V[i]在SPT中，则添加到SPT中if(V_idx[i] == 0 && V[i] >= 0&& V_idx[V[i]] == 1 &&spt.addChild(V[i], i, new ElemItem<Double>(D[i]))){V_idx[i] = 1;f = 1;}}// 一次都没有添加，结束循环if(f == -1) break;}}算法中每次从SPT之外的顶点中选择一个顶点v，对应边的权值最小；然后对这条边进行松弛操作。
算法迭代直至图中所有顶点都在SPT中为止。
以图为例，求解图的最短路径树，起始顶点为顶点0。
根据算法实现过程，提取图中最短路径数的过程如图(a-c)。
算法初始化阶段每个顶点到起始顶点s的最短路径长度为∞。
首先从起始顶点0开始，寻找相邻顶点1和顶点5，并对其进行松弛操作。
此时SPT中根节点为0，两个（未确定）子节点为顶点1和顶点5。
其中顶点0着色为灰色（赋值1），只有着色为灰色的顶点确定为SPT 中顶点。
由于顶点1和顶点5对应的边可能会在以后的操作中进行松弛操作，所以SPT中这两个顶点是未确定的，顶点着色也未改变。
选择与当前SPT中顶点0最近的顶点5，首先将顶点5确定为SPT中顶点0的子节点；然后对其相邻顶点进行松弛操作。
相邻顶点为顶点1和顶点4，其中顶点4的最短距离需要更新。
选择与当前SPT中顶点0、顶点5最近的顶点4，首先将顶点4确定为SPT中顶点5的子节点；然后对其相邻顶点进行松弛操作。
相邻顶点为顶点2和顶点3，这两个顶点都需要更新最短距离。
接下来将先后选择边(5, 1)、(4, 2)和(4, 3)，并进行松弛操作。
最终得到的SPT为：将图作为算法代码的测试输入，编写示例程序如下：public class DijkstraExample {public static void main(String args[]){GraphLnk GL =Utilities.BulidGraphLnkFromFile("Graph\\graph8.txt");SingleSourceShortestPaths sp =new SingleSourceShortestPaths(GL);sp.Dijkstra(0);sp.spt.ford_print_tree();}}算法跟踪顶点选择和边松弛操作的过程，每个顶点距离起始顶点的最短距离记录在数组D中，顶点的父节点保存在数组V中，最终利用前面章节中讨论的广义树存放SPT。
