最短路径和最小生成树的区别：最短路径解决的是如何求解各顶点之间的路径权值和最小的问题。最小生成树是保证图的所有路径权值之和最小，并不能保证顶点之间的路径权值和是最小的。
测试图：
最短路径测试图.png
对应的最短路径图：
最短路径.png
迪杰斯特拉算法(Dijkstra)
思想：若要求的是v0到v8的最短路径，则是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到想要的结果。
源代码：
// 图的最短路径--dijkstra算法
public void ShortestPath_Dijkstra(MyGraph graph, int v0) {
int v, w, k, min;
k = 0;
// 前驱顶点数组,prev[2] = 1表示顶点2的前驱是顶点1
int[] prev = new int[getNumOfVertex()];
// 路径权值数组,dist[3] = 4表示v0顶点到v3顶点的路径权值为4
int[] dist = new int[getNumOfVertex()];
// flag[i] = true表示已求得v0到vi顶点的最短路径
boolean[] flag = new boolean[getNumOfVertex()];
// 初始化各数组
for (v = 0; v < getNumOfVertex(); v++) {
prev[v] = 0;
// dist数组初始化为与v0顶点相连的边的权值
dist[v] = edges[v0][v];
flag[v] = false;
}
// v0到v0的路径为0
dist[v0] = 0;
// v0到v0不需要求路径
flag[v0] = true;
for (v = 1; v < getNumOfVertex(); v++) {
// min初始化为65535
min = INF;
// 每次循环求得v0到某个顶点的最短路径
for (w = 0; w < getNumOfVertex(); w++) {
if (flag[w] == false && dist[w] < min) {
// w顶点离v0顶点更近
k = w;
min = dist[w];
}
}
flag[k] = true;
// 修正当前最短路径以及前驱顶点，即修改dist和prev数组的值
for (w = 0; w < getNumOfVertex(); w++) {
// k:离v0顶点最近的顶点;
// dist[w]:v0直连到顶点w的权值
if (flag[w] == false && (min + edges[k][w] < dist[w])) {
dist[w] = min + edges[k][w];
prev[w] = k;
}
}
}
// 输出v0顶点到各顶点的最短路径的权值以及各顶点的前驱顶点
for (int i = 0; i < getNumOfVertex(); i++) {
System.out.println(getValueByIndex(v0) + "->" + getValueByIndex(i) + " : " + dist[i]);
}
for (int i = 0; i < getNumOfVertex(); i++) {
System.out.print("prev[" + i + "] = " + prev[i] +"; ");
}
}
测试程序：
int n = 9;
MyGraph graph = new MyGraph(n);
String[] vertex = {"v0","v1","v2","v3","v4","v5","v6","v7","v8"};
for (String string : vertex) {
graph.insertVertex(string);
}
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 5);
graph.insertEdge(1, 2, 3);
graph.insertEdge(1, 3, 7);
graph.insertEdge(1, 4, 5);
graph.insertEdge(2, 4, 1);
graph.insertEdge(2, 5, 7);
graph.insertEdge(3, 4, 2);
graph.insertEdge(3, 6, 3);
graph.insertEdge(4, 5, 3);
graph.insertEdge(4, 6, 6);
graph.insertEdge(4, 7, 9);
graph.insertEdge(5, 7, 5);
graph.insertEdge(6, 7, 2);
graph.insertEdge(6, 8, 7);
graph.insertEdge(7, 8, 4);
graph.ShortestPath_Dijkstra(graph, 0);
测试结果：
迪杰斯特拉算法测试结果图.png
从测试结果可以看出v0顶点到各顶点的最短路径的权值。
如果我们想知道v8->v0的具体路径，我们从prev[]数组中可以得到prev[8]=7,说明顶点8的前驱顶点是顶点7，并由prev[7]=6，prev[6]=3，prev[3]=4，prev[4]=2，prev[2]=1，prev[1]=0可以得出具体路径,即v0到v8的最短路径为v0->v1->v2->v4->v3->v6->v7->v8。
弗洛伊德算法(Floyd)
弗洛伊德算法解决的是所有顶点到所有顶点的最短路径问题
思想：弗洛伊德算法通过两个二维数组分别代表所有顶点到所有顶点的最短路径权值和以及对应顶点的最小路径的前驱顶点。
源代码：
// 最短路径--弗洛伊德算法
public void ShortestPath_Floyd(MyGraph graph) {
int v, k, w;
//dist二维数组存放所有顶点到所有顶点的最短路径权值和
int[][] dist = new int[getNumOfVertex()][getNumOfVertex()];
//prev二维数组存放所有顶点到所有顶点的最短路径的前驱顶点
int[][] prev = new int[getNumOfVertex()][getNumOfVertex()];
for (v = 0; v < getNumOfVertex(); v++) {
for (w = 0; w < getNumOfVertex(); w++) {
//dist初始化为邻接矩阵
dist[v][w] = edges[v][w];
prev[v][w] = w;
}
}
//弗洛伊德算法求得是所有顶点到所有顶点的最短路径，所以需要遍历所有的顶点
for (k = 0; k < getNumOfVertex(); k++) {
for (v = 0; v < getNumOfVertex(); v++) {
for (w = 0; w < getNumOfVertex(); w++) {
//k=0表示所有的顶点都经过v0顶点中转
//例如：v0->v1=2;v0->v2=1;v1->v2=5;当v0->v2 > (v0->v1) + (v1->v2)时条件成立
if (dist[v][w] > dist[v][k] + dist[k][w]) {
//修改v->w的最短路径权值
dist[v][w] = dist[v][k] + dist[k][w];
//修改v->w的最短路径中w顶点的前驱顶点为顶点k
prev[v][w] = prev[v][k];
}
}
}
}
//输出dist数组
// System.out.println("dist数组的值如下：");
// for (v = 0; v < getNumOfVertex(); v++) {
// for (w = 0; w < getNumOfVertex(); w++) {
// if (w == getNumOfVertex() - 1) {
// System.out.println("\t" + dist[v][w]);
// } else {
// System.out.print("\t" + dist[v][w]);
// }
// }
// }
//输出prev数组
// System.out.println("\nprev数组的值如下：");
// for (v = 0; v < getNumOfVertex(); v++) {
// for (w = 0; w < getNumOfVertex(); w++) {
// if (w == getNumOfVertex() - 1) {
// System.out.println("\t" + prev[v][w]);
// } else {
// System.out.print("\t" + prev[v][w]);
// }
// }
// }
// PrintAllShortestPath_Floyd(dist, prev);
// }
//输出所有顶点到所有顶点的最短路径
// public void PrintAllShortestPath_Floyd(int[][] dist, int[][] prev) {
// for(int v = 0; v < getNumOfVertex(); v++) {
// for(int w = v+1; w < getNumOfVertex(); w++) {
// System.out.print(getValueByIndex(v)+"->"+getValueByIndex(w)+" 权值: "+dist[v][w]);
// int k = prev[v][w];
// System.out.print(" 路径："+getValueByIndex(v));
// while(k != w) {
// System.out.print(" -> "+getValueByIndex(k));
// k = prev[k][w];
// }
// System.out.println(" -> "+getValueByIndex(w));
// }
// System.out.println("\n");
// }
测试程序：
int n = 9;
MyGraph graph = new MyGraph(n);
String[] vertex = {"v0","v1","v2","v3","v4","v5","v6","v7","v8"};
for (String string : vertex) {
graph.insertVertex(string);
}
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 5);
graph.insertEdge(1, 2, 3);
graph.insertEdge(1, 3, 7);
graph.insertEdge(1, 4, 5);
graph.insertEdge(2, 4, 1);
graph.insertEdge(2, 5, 7);
graph.insertEdge(3, 4, 2);
graph.insertEdge(3, 6, 3);
graph.insertEdge(4, 5, 3);
graph.insertEdge(4, 6, 6);
graph.insertEdge(4, 7, 9);
graph.insertEdge(5, 7, 5);
graph.insertEdge(6, 7, 2);
graph.insertEdge(6, 8, 7);
graph.insertEdge(7, 8, 4);
graph.ShortestPath_Floyd(graph);
测试结果：
弗洛伊德算法矩阵图.png
dist数组每一行表示当前顶点到其他顶点最短路径的权值和。
prev数组每一列表示当前顶点到对应的顶点最短路径的前驱顶点，如prev[0][5]=1,prev[1][5]=2,prev[2][5]=4,prev[4][5]=5,即v0到v5顶点的最短路径为v0->v1->v2->v4->v5;
弗洛伊德算法所有顶点到所有顶点的最短路径图.png
时间复杂度
迪杰斯特拉算法求最短路径时的时间复杂度是O(n^2), 当其求所有顶点到所有顶点的时候，时间复杂度是O(n^3); 弗洛伊德算法的时间复杂度是O(n^3),代码简洁但不便于理解，迪杰斯特拉代码较为复杂但是容易理解。
