1) 胜利乡有 村庄 (A, B, C, D, E, F, G，H，I，J) ，现在有 9 个邮差，从 G 点出发，需要分别把邮件分别送到 A, B, C , D, E, F ，H，I，J 9个村庄。 2) 各个村庄的距离用边线表示 ( 权 ) ，比如 A – B 距离 5 公里 3) 问：如何计算出 G 村庄到 其它各个村庄的最短距离 ? 4) 如果从其它点出发到各个点的最短距离又是多少 ? 二、迪杰斯特拉算法Dijkstra
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
设置出发顶点为v，顶点集合V{v1,v2,vi...}，v到V中各顶点的距离构成距离集合Dis，Dis{d1,d2,di...}，Dis集合记录着v到图中各顶点的距离(到自身可以看作0，v到vi距离对应为di)
1) 从 Dis 中选择值最小的 di 并移出 Dis 集合，同时移出 V 集合中对应的顶点 vi ，此时的 v 到 vi 即为最短路径 2) 更新 Dis 集合，更新规则为：比较 v 到 V 集合中顶点的距离值，与 v 通过 vi 到 V 集合中顶点的距离值，保留值较小的一个 ( 同时也应该更新顶点的前驱节点为 vi ，表明是通过 vi 到达的 ) 3) 重复执行两步骤，直到最短路径顶点为目标顶点即可结束
算法的通俗理解：
1.先定义 距离数组 和 已访问数组，并且初始化：与 G 点相关的权值照常填进去，而不关联的权值都设为极大值，如 65536 ，用于后面比较大小。注：G 到它本身的距离应始终设为0
2.从 距离数组 中挑出 权值最小且 未被访问的点 ， 更新距离数组和已访问数组。这里是重点！ 2.1 用一个变量保存该点到其它点的权值。这个变量是临时的！！ 2.2 用该点到其它点的权值 加上从 出发点到该点的权值。 2.3 比较相加后的权值与原来的大小，取 较小的一个，更新到距离数组中。 2.4 标记已访问 *比如G是出发点，则 G->A ,而 A->C ，那么就可以 把 A 当做中介 ，求出 G->C，进而更新从G出发到与A关联的所有点的距离。这就是一个动态规划的过程。 3. 重复 2 直到所有点都被访问 三、弗洛依德算法Floyd弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径；弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。
弗洛伊德(Floyd)算法图解分析
1) 设置顶点 vi 到顶点 vk 的最短路径已知为 Lik ，顶点 vk 到 vj 的最短路径已知为 Lkj ，顶点 vi 到 vj 的路径为 Lij ，则 vi 到 vj 的最短路径为： min((Lik+Lkj),Lij) ， vk 的取值为图中所有顶点，则可获得 vi 到 vj 的最短路径 2) 至于 vi 到 vk 的最短路径 Lik 或者 vk 到 vj 的最短路径 Lkj ，是以同样的方式获得 通俗理解： 例如A、B、C三个点， B 是 A、C的中间顶点。 A->C、 A->B->C 都可行，那就对比两者路径长度，取 较小的一个作为 A->B 的最短路径。 采用三个循环，外循环为 中间顶点，内循环分别为 出发点和 终点。不断更新 距离数组就行了（这里是二维数组）。这样最后就可以得到 任意两点的最短距离。 四、代码演示 4.1 图的定义class Graph {
protected List vertex;//存放顶点
protected int[][] edges;//存放边
protected boolean[] isVisited;//是否被访问
protected int numOfEdges;
public Graph(int n) {
this.vertex = new ArrayList<>(n);
this.edges = new int[n][n];
this.isVisited = new boolean[n];
}
//常用方法
// 1. 获取节点个数
protected int getNumOfVertex() {
return vertex.size();
}
// 2. 打印邻接矩阵
protected void printGraph() {
System.out.print(" ");
for (String s : vertex) System.out.print(" " + s);
System.out.println();
for (int r = 0; r < vertex.size(); r++) {
System.out.print(vertex.get(r) + " ");
for (int c = 0; c < vertex.size(); c++) {
System.out.print(String.format("%5d",edges[r][c]) + " ");
}
System.out.println();
}
System.out.println();
}
// 3. 获取边的数目
protected int getNumOfEdges() {
return numOfEdges;
}
// 4. 获取某条边的权值
protected int getWeightOfEdges(int v1, int v2) {
return edges[v1][v2];
}
// 5. 添加节点
protected void addVertex(String v) {
vertex.add(v);
}
// 6. 添加边（双向）
protected void addEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
// 7.获取顶点索引对应的值
protected String getValueByIndex(int i) {
return vertex.get(i);
}
}
4.2 迪杰斯特拉算法求最短路径
//*****************************迪杰斯特拉算法*********************************************
public static void Dijkstra(Graph graph, int v) {
int[] distance = new int[graph.getNumOfVertex()];//顶点v到其他各顶点的距离
int[] visited = new int[graph.getNumOfVertex()];//存储中间的遍历结果
// 一、初始化
init(v, distance, visited, graph);
// 二、循环更新距离直到所有点都被遍历
while (!ifEnd(visited)) {
update(getMinDistanceIndex(distance, visited, v), visited, distance, graph, v);
}
}
// 1.初始化（初始顶点需特殊处理）
public static void init(int beginIndex, int[] distance, int[] visited, Graph graph) {
for (int i = 0; i < distance.length; i++) {
if (graph.edges[beginIndex][i] != 0) distance[i] = graph.edges[beginIndex][i];//先获得原始的距离数组
}
distance[beginIndex] = 0;//距起始点的距离始终为0，后面更新时要额外注意避免修改
visited[beginIndex] = 1;//起始点标记已访问
System.out.println("初始化...................");
System.out.println("距离：");
System.out.println(Arrays.toString(distance));
System.out.println("已访问顶点：");
System.out.println(Arrays.toString(visited));
System.out.println();
}
// 2.返回distance中距离最短并未被访问的顶点索引
public static int getMinDistanceIndex(int[] distance, int[] visited, int v) {
int minDis = 65536;//假定最小值
int minDisIndex = 0;
for (int i = 0; i < distance.length; i++) {
if (distance[i] < minDis && i != v && visited[i] == 0) {//要找未访问的点，同时不可以是出发点！
minDis = distance[i];
minDisIndex = i;
}
}
return minDisIndex;
}
// 3.更新操作，每次都更新距离数组和已访问数组(重点难点在于更新距离)
public static void update(int index, int[] visited, int[] distance, Graph graph, int v) {
Map modifiedVertex=new HashMap<>();
int[] tempDis = new int[distance.length];
//首先把index对应点与其他点的距离保存在临时变量中
for (int i = 0; i < graph.getNumOfVertex(); i++) {
if (graph.edges[index][i] != 0) {
tempDis[i] = graph.edges[index][i];
}
}
//修改距离，要加上从出发点到index顶点的距离。注意原始出发点不能动！
for (int k = 0; k < graph.getNumOfVertex(); k++) {
if (tempDis[k] != 65536 && k != v) {
tempDis[k] += distance[index];
}
}
//修改后的距离如果比原来的小，就更新distance，同样不能动原始出发点！（感觉这里像是动态规划的思想，需要动态调整到所有点的距离）
for (int j = 0; j < graph.getNumOfVertex(); j++) {
if (tempDis[j] < distance[j] && j != v) {
modifiedVertex.put(graph.getValueByIndex(j),distance[j]+"->"+tempDis[j]);
distance[j] = tempDis[j];
}
}
//标记这个点已访问
visited[index] = 1;
//输出本次的更新结果
System.out.println();
System.out.print("距离： ");
System.out.println(Arrays.toString(distance));
System.out.print("更新距离： ");
if(modifiedVertex.isEmpty()) System.out.print("本次未更新");
else for(Map.Entryentry:modifiedVertex.entrySet())
System.out.print(entry.getKey()+":"+entry.getValue()+" ");
System.out.println();
System.out.print("已访问顶点： ");
System.out.println(Arrays.toString(visited));
}
// 4.判断已访问数组是否满，满了就结束
public static Boolean ifEnd(int[] visited) {
for (int i = 0; i < visited.length; i++) {
if (visited[i] == 0) {
return false;
}
}
return true;
}
测试：
@Test
public void testDijkstra() {
Graph graph = new Graph(10);
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");
graph.addVertex("G");
graph.addVertex("H");
graph.addVertex("I");
graph.addVertex("J");
graph.addEdge(0, 1, 5);
graph.addEdge(0, 2, 7);
graph.addEdge(0, 6, 2);
graph.addEdge(1, 6, 3);
graph.addEdge(1, 3, 9);
graph.addEdge(2, 4, 8);
graph.addEdge(3, 5, 4);
graph.addEdge(4, 5, 5);
graph.addEdge(4, 6, 4);
graph.addEdge(5, 6, 6);
graph.addEdge(4, 7, 5);
graph.addEdge(5, 7, 5);
graph.addEdge(5, 8, 4);
graph.addEdge(7, 8, 3);
graph.addEdge(3, 9, 6);
graph.addEdge(8, 9, 2);
//权为0的边权都等于65536.
for (int i = 0; i < graph.getNumOfVertex(); i++) {
for (int j = 0; j < graph.getNumOfVertex(); j++) {
if (graph.edges[i][j] == 0) graph.edges[i][j] = 65536;
}
}
System.out.println("边的数量： " + graph.getNumOfEdges());
System.out.println("顶点的数量： " + graph.getNumOfVertex());
System.out.println("邻接矩阵：");
graph.printGraph();
minRoute.Dijkstra(graph, 6);
}
边的数量： 16
顶点的数量： 10
邻接矩阵：
A B C D E F G H I J
A 65536 5 7 65536 65536 65536 2 65536 65536 65536
B 5 65536 65536 9 65536 65536 3 65536 65536 65536
C 7 65536 65536 65536 8 65536 65536 65536 65536 65536
D 65536 9 65536 65536 65536 4 65536 65536 65536 6
E 65536 65536 8 65536 65536 5 4 5 65536 65536
F 65536 65536 65536 4 5 65536 6 5 4 65536
G 2 3 65536 65536 4 6 65536 65536 65536 65536
H 65536 65536 65536 65536 5 5 65536 65536 3 65536
I 65536 65536 65536 65536 65536 4 65536 3 65536 2
J 65536 65536 65536 6 65536 65536 65536 65536 2 65536
初始化...................
距离：
[2, 3, 65536, 65536, 4, 6, 0, 65536, 65536, 65536]
已访问顶点：
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
距离： [2, 3, 9, 65536, 4, 6, 0, 65536, 65536, 65536]
更新距离： C:65536->9
已访问顶点： [1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
距离： [2, 3, 9, 12, 4, 6, 0, 65536, 65536, 65536]
更新距离： D:65536->12
已访问顶点： [1, 1, 0, 0, 0, 0, 1, 0, 0, 0]
距离： [2, 3, 9, 12, 4, 6, 0, 9, 65536, 65536]
更新距离： H:65536->9
已访问顶点： [1, 1, 0, 0, 1, 0, 1, 0, 0, 0]
距离： [2, 3, 9, 10, 4, 6, 0, 9, 10, 65536]
更新距离： D:12->10 I:65536->10
已访问顶点： [1, 1, 0, 0, 1, 1, 1, 0, 0, 0]
距离： [2, 3, 9, 10, 4, 6, 0, 9, 10, 65536]
更新距离： 本次未更新
已访问顶点： [1, 1, 1, 0, 1, 1, 1, 0, 0, 0]
距离： [2, 3, 9, 10, 4, 6, 0, 9, 10, 65536]
更新距离： 本次未更新
已访问顶点： [1, 1, 1, 0, 1, 1, 1, 1, 0, 0]
距离： [2, 3, 9, 10, 4, 6, 0, 9, 10, 16]
更新距离： J:65536->16
已访问顶点： [1, 1, 1, 1, 1, 1, 1, 1, 0, 0]
距离： [2, 3, 9, 10, 4, 6, 0, 9, 10, 12]
更新距离： J:16->12
已访问顶点： [1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
距离： [2, 3, 9, 10, 4, 6, 0, 9, 10, 12]
更新距离： 本次未更新
已访问顶点： [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
4.3 弗洛伊德算法求最短路径
//*****************************弗洛伊德算法*********************************************
public static void Floyd(Graph graph) {
int[][] distance = graph.edges;//记录各顶点间的距离
// mid-中间顶点 begin-起始顶点 end-终点顶点
for(int mid=0;midC->B 的距离比 A->B 的距离短，就更新A、B间的距离
int newDis=distance[begin][mid]+distance[mid][end];
if(distance[begin][end]>newDis && begin!=end){
System.out.println("修改距离："+graph.getValueByIndex(begin)+"->"+graph.getValueByIndex(end)
+" "+distance[begin][end]+", 修改为 :"+newDis);
distance[begin][end]=newDis;
distance[end][begin]=newDis;//更新距离,对于无向图 Lij=Lji
}
}
}
}
//结果展示
System.out.println(" "+"各个顶点间的最终最短距离：");
for(int i=0;i"+graph.getValueByIndex(j)+" "+distance[i][j]+",");
}
System.out.println("n");
}
}
测试：
@Test
public void testFloyd() {
Graph graph = new Graph(10);
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");
graph.addVertex("G");
graph.addVertex("H");
graph.addVertex("I");
graph.addVertex("J");
graph.addEdge(0, 1, 5);
graph.addEdge(0, 2, 7);
graph.addEdge(0, 6, 2);
graph.addEdge(1, 6, 3);
graph.addEdge(1, 3, 9);
graph.addEdge(2, 4, 8);
graph.addEdge(3, 5, 4);
graph.addEdge(4, 5, 5);
graph.addEdge(4, 6, 4);
graph.addEdge(5, 6, 6);
graph.addEdge(4, 7, 5);
graph.addEdge(5, 7, 5);
graph.addEdge(5, 8, 4);
graph.addEdge(7, 8, 3);
graph.addEdge(3, 9, 6);
graph.addEdge(8, 9, 2);
//权为0的边权都等于65536.
for (int i = 0; i < graph.getNumOfVertex(); i++) {
for (int j = 0; j < graph.getNumOfVertex(); j++) {
if (graph.edges[i][j] == 0) graph.edges[i][j] = 65536;
}
}
System.out.println("边的数量： " + graph.getNumOfEdges());
System.out.println("顶点的数量： " + graph.getNumOfVertex());
System.out.println("邻接矩阵：");
graph.printGraph();
minRoute_.Floyd(graph);
}
边的数量： 16
顶点的数量： 10
邻接矩阵：
A B C D E F G H I J
A 65536 5 7 65536 65536 65536 2 65536 65536 65536
B 5 65536 65536 9 65536 65536 3 65536 65536 65536
C 7 65536 65536 65536 8 65536 65536 65536 65536 65536
D 65536 9 65536 65536 65536 4 65536 65536 65536 6
E 65536 65536 8 65536 65536 5 4 5 65536 65536
F 65536 65536 65536 4 5 65536 6 5 4 65536
G 2 3 65536 65536 4 6 65536 65536 65536 65536
H 65536 65536 65536 65536 5 5 65536 65536 3 65536
I 65536 65536 65536 65536 65536 4 65536 3 65536 2
J 65536 65536 65536 6 65536 65536 65536 65536 2 65536
A作为中间顶点...
修改距离：B->C 65536, 修改为 :12
修改距离：C->G 65536, 修改为 :9
B作为中间顶点...
修改距离：A->D 65536, 修改为 :14
修改距离：C->D 65536, 修改为 :21
修改距离：D->G 65536, 修改为 :12
C作为中间顶点...
修改距离：A->E 65536, 修改为 :15
修改距离：B->E 65536, 修改为 :20
修改距离：D->E 65536, 修改为 :29
D作为中间顶点...
修改距离：A->F 65536, 修改为 :18
修改距离：A->J 65536, 修改为 :20
修改距离：B->F 65536, 修改为 :13
修改距离：B->J 65536, 修改为 :15
修改距离：C->F 65536, 修改为 :25
修改距离：C->J 65536, 修改为 :27
修改距离：E->J 65536, 修改为 :35
修改距离：F->J 65536, 修改为 :10
修改距离：G->J 65536, 修改为 :18
E作为中间顶点...
修改距离：A->H 65536, 修改为 :20
修改距离：B->H 65536, 修改为 :25
修改距离：C->F 25, 修改为 :13
修改距离：C->H 65536, 修改为 :13
修改距离：D->H 65536, 修改为 :34
修改距离：G->H 65536, 修改为 :9
修改距离：H->J 65536, 修改为 :40
F作为中间顶点...
修改距离：A->I 65536, 修改为 :22
修改距离：B->E 20, 修改为 :18
修改距离：B->H 25, 修改为 :18
修改距离：B->I 65536, 修改为 :17
修改距离：C->D 21, 修改为 :17
修改距离：C->I 65536, 修改为 :17
修改距离：C->J 27, 修改为 :23
修改距离：D->E 29, 修改为 :9
修改距离：D->G 12, 修改为 :10
修改距离：D->H 34, 修改为 :9
修改距离：D->I 65536, 修改为 :8
修改距离：E->I 65536, 修改为 :9
修改距离：E->J 35, 修改为 :15
修改距离：G->I 65536, 修改为 :10
修改距离：G->J 18, 修改为 :16
修改距离：H->J 40, 修改为 :15
G作为中间顶点...
修改距离：A->D 14, 修改为 :12
修改距离：A->E 15, 修改为 :6
修改距离：A->F 18, 修改为 :8
修改距离：A->H 20, 修改为 :11
修改距离：A->I 22, 修改为 :12
修改距离：A->J 20, 修改为 :18
修改距离：B->E 18, 修改为 :7
修改距离：B->F 13, 修改为 :9
修改距离：B->H 18, 修改为 :12
修改距离：B->I 17, 修改为 :13
H作为中间顶点...
修改距离：C->I 17, 修改为 :16
修改距离：E->I 9, 修改为 :8
I作为中间顶点...
修改距离：A->J 18, 修改为 :14
修改距离：C->J 23, 修改为 :18
修改距离：E->J 15, 修改为 :10
修改距离：F->J 10, 修改为 :6
修改距离：G->J 16, 修改为 :12
修改距离：H->J 15, 修改为 :5
J作为中间顶点...
各个顶点间的最终最短距离：
A->B 5, A->C 7, A->D 12, A->E 6, A->F 8, A->G 2, A->H 11, A->I 12, A->J 14,
B->A 5, B->C 12, B->D 9, B->E 7, B->F 9, B->G 3, B->H 12, B->I 13, B->J 15,
C->A 7, C->B 12, C->D 17, C->E 8, C->F 13, C->G 9, C->H 13, C->I 16, C->J 18,
D->A 12, D->B 9, D->C 17, D->E 9, D->F 4, D->G 10, D->H 9, D->I 8, D->J 6,
E->A 6, E->B 7, E->C 8, E->D 9, E->F 5, E->G 4, E->H 5, E->I 8, E->J 10,
F->A 8, F->B 9, F->C 13, F->D 4, F->E 5, F->G 6, F->H 5, F->I 4, F->J 6,
G->A 2, G->B 3, G->C 9, G->D 10, G->E 4, G->F 6, G->H 9, G->I 10, G->J 12,
H->A 11, H->B 12, H->C 13, H->D 9, H->E 5, H->F 5, H->G 9, H->I 3, H->J 5,
I->A 12, I->B 13, I->C 16, I->D 8, I->E 8, I->F 4, I->G 10, I->H 3, I->J 2,
J->A 14, J->B 15, J->C 18, J->D 6, J->E 10, J->F 6, J->G 12, J->H 5, J->I 2,
以G点为例
五、总结迪杰斯特拉算法的关键是更新距离数组 distance[ ] ，每个遍历到的点相当于 一个中介，利用它到起始点的距离来更新与之邻接的其他点与起始点的距离。
弗洛伊德算法最容易理解，把某点当做中间顶点，更新以它为中介的两个点间的距离，也是更新 distance[][] 数组。
两个算法用到的 distance数组的区别在于一维的只记录 一个点到其它点的距离，而二维的记录的是所有点间的距离。
