首页 > 算法 阅读：1152

迪杰斯特拉算法求最短路径（超级详细，图文并茂）

< 上一节下一节 >
通义灵码
迪杰斯特拉算法用于查找图中某个顶点到其它所有顶点的最短路径，该算法既适用于无向加权图，也适用于有向加权图。

注意，使用迪杰斯特拉算法查找最短路径时，必须保证图中所有边的权值为非负数，否则查找过程很容易出错。

迪杰斯特拉算法的实现思路

图 1 是一个无向加权图，我们就以此图为例，给大家讲解迪杰斯特拉算法的实现思路。

无向加权图
图 1 无向加权图

假设用迪杰斯特拉算法查找从顶点 0 到其它顶点的最短路径，具体过程是：
1) 统计从顶点 0 直达其它顶点的权值，如下表所示：

表 1 顶点 0 直达其它顶点的权值
  1 2 3 4 5 6
总权值 2 6 ∞ ∞ ∞ ∞
路径 0-1 0-2 0-3 0-4 0-5 0-6

∞ 表示两个顶点之间无法直达，对应的权值为无穷大。

2) 表 1 中，权值最小的是 0-1 路径，它也是从顶点 0 到顶点 1 的最短路径（如图 2 所示）。原因很简单，从顶点 0 出发一共只有 0-1 和 0-2 两条路径，0-2 的权值本就比 0-1 大，所以从 0-2 出发不可能找得到比 0-1 权值更小的路径。

最短路径 0-1
图 2 最短路径 0-1

3) 找到最短路径 0-1 后，沿 0-1 路径方向查找更短的到达其它顶点的路径，并对表 1 进行更新。

表 2 沿 0-1 最短路径更新表 1
  1 2 3 4 5 6
总权值 2 6 2+5 ∞ ∞ ∞
路径 0-1 0-2 0-1-3 0-4 0-5 0-6

绿色加粗的权值是已确认为最短路径的权值，后续选择总权值最小的路径时不再重复选择；红色加粗的权值为刚刚更新的权值。

更新后的表格如表 2 所示，沿 0-1 路径可以到达顶点 3，且 0-1-3 的总权值比 0-3 更小。表 2 中，总权值最小的路径是 0-2，它也是从顶点 0 到顶点 2 的最短路径，如下图所示。

最短路径 0-2
图 3 最短路径 0-2

4) 重复之前的操作，沿 0-2 路径方向查找更短的到达其它顶点的路径。遗憾地是，从顶点 2 只能到达顶点 3，且 0-2-3 的总权值比表 2 中记录的 0-1-3 更大，因此表 2 中记录的数据维持不变。

表 3 结合 0-2 最短路径更新表 2
  1 2 3 4 5 6
总权值 2 6 7 ∞ ∞ ∞
路径 0-1 0-2 0-1-3 0-4 0-5 0-6

5) 表 3 中，总权值最小的是 0-1-3，它也是顶点 0 到顶点 3 的最短路径。

最短路径 0-1-3
图 4 最短路径 0-1-3

沿 0-1-3 路径方向，查找到其它顶点更短的路径并更新表 3。更新后的表格为：

表 4 结合 0-1-3 最短路径更新表 3
  1 2 3 4 5 6
总权值 2 6 7 7+10 7+15 ∞
路径 0-1 0-2 0-1-3 0-1-3-4 0-1-3-5 0-6

6) 表 4 中，总权值最小的是 0-1-3-4，它是顶点 0 到顶点 4 的最短路径。

最短路径 0-1-3-4
图 5 最短路径 0-1-3-4

从顶点 4 出发，查找顶点 0 到其它顶点更短的路径并更新表 4。更新后的表格为：

表 5 结合 0-1-3-4 最短路径更新表 4
  1 2 3 4 5 6
总权值 2 6 7 17 22 17+2
路径 0-1 0-2 0-1-3 0-1-3-4 0-1-3-5 0-1-3-4-6

7) 表 5 中，总权值最小的路径是 0-1-3-4-6，它是顶点 0 到顶点 6 的最短路径。

最短路径 0-1-3-4-6
图 6 最短路径 0-1-3-4-6

8) 从图 6 可以看到，只剩下顶点 0 到顶点 5 的最短路径尚未确定。从顶点 6 出发到达顶点 5 的路径是 0-1-3-4-6-5，对应的总权值为 25，大于表 5 中记录的 0-1-3-5 路径，因此 0-1-3-5 是顶点 0 到顶点 5 的最短路径。

最短路径 0-1-3-5
图 7 最短路径 0-1-3-5

由此借助迪杰斯特拉算法，我们找出了顶点 0 到其它所有顶点的最短路径，如下表所示：

表 6 最短路径
  1 2 3 4 5 6
总权值 2 6 7 17 22 19
路径 0-1 0-2 0-1-3 0-1-3-4 0-1-3-5 0-1-3-4-6

迪杰斯特拉算法的具体实现

了解了迪杰斯特拉算法的实现过程之后，接下来分别编写 C、Java 和 Python 程序真正地实现迪杰斯特拉算法。

仍以图 1 为例，迪杰斯特拉算法查找顶点 0 到其它顶点所有最短路径的 C 语言程序为： 
  1. #include <stdio.h>
  2. #define V 20                   //顶点的最大个数
  3. #define INFINITY 65535
  4. typedef struct {
  5.     int vexs[V];         //存储图中顶点数据
  6.     int arcs[V][V];      //二维数组，记录顶点之间的关系
  7.     int vexnum, arcnum;  //记录图的顶点数和弧（边）数
  8. }MGraph;
  9.  
  10. //根据顶点本身数据，判断出顶点在二维数组中的位置
  11. int LocateVex(MGraph * G, int v) {
  12.     int i = 0;
  13.     //遍历一维数组，找到变量v
  14.     for (; i < G->vexnum; i++) {
  15.         if (G->vexs[i] == v) {
  16.             break;
  17.         }
  18.     }
  19.     //如果找不到，输出提示语句，返回-1
  20.     if (i > G->vexnum) {
  21.         printf("no such vertex.\n");
  22.         return -1;
  23.     }
  24.     return i;
  25. }
  26. //构造无向有权图
  27. void CreateDG(MGraph *G) {
  28.     printf("输入图的顶点数和边数：");
  29.     scanf("%d %d", &(G->vexnum), &(G->arcnum));
  30.     printf("输入各个顶点：");
  31.     for (int i = 0; i < G->vexnum; i++) {
  32.         scanf("%d", &(G->vexs[i]));
  33.     }
  34.     for (int i = 0; i < G->vexnum; i++) {
  35.         for (int j = 0; j < G->vexnum; j++) {
  36.             G->arcs[i][j] = INFINITY;
  37.         }
  38.     }
  39.     printf("输入各个边的数据：\n");
  40.     for (int i = 0; i < G->arcnum; i++) {
  41.         int v1, v2, w;
  42.         scanf("%d %d %d", &v1, &v2, &w);
  43.         int n = LocateVex(G, v1);
  44.         int m = LocateVex(G, v2);
  45.         if (m == -1 || n == -1) {
  46.             return;
  47.         }
  48.         G->arcs[n][m] = w;
  49.         G->arcs[m][n] = w;
  50.     }
  51. }
  52. //迪杰斯特拉算法，v0表示有向网中起始点所在数组中的下标
  53. void Dijkstra_minTree(MGraph G, int v0, int p[V], int D[V]) {
  54.     int final[V];//为各个顶点配置一个标记值，用于确认该顶点是否已经找到最短路径
  55.     //对各数组进行初始化
  56.     for (int v = 0; v < G.vexnum; v++) {
  57.         final[v] = 0;
  58.         D[v] = G.arcs[v0][v];
  59.         p[v] = 0;
  60.     }
  61.     //由于以v0位下标的顶点为起始点，所以不用再判断
  62.     D[v0] = 0;
  63.     final[v0] = 1;
  64.     int k = 0;
  65.     for (int i = 0; i < G.vexnum; i++) {
  66.         int min = INFINITY;
  67.         //选择到各顶点权值最小的顶点，即为本次能确定最短路径的顶点
  68.         for (int w = 0; w < G.vexnum; w++) {
  69.             if (!final[w]) {
  70.                 if (D[w] < min) {
  71.                     k = w;
  72.                     min = D[w];
  73.                 }
  74.             }
  75.         }
  76.         //设置该顶点的标志位为1，避免下次重复判断
  77.         final[k] = 1;
  78.         //对v0到各顶点的权值进行更新
  79.         for (int w = 0; w < G.vexnum; w++) {
  80.             if (!final[w] && (min + G.arcs[k][w] < D[w])) {
  81.                 D[w] = min + G.arcs[k][w];
  82.                 p[w] = k;//记录各个最短路径上存在的顶点
  83.             }
  84.         }
  85.     }
  86. }
  87. int main() {
  88.     MGraph G;
  89.     CreateDG(&G);
  90.     int P[V] = { 0 };   // 记录顶点 0 到各个顶点的最短的路径
  91.     int D[V] = { 0 };   // 记录顶点 0 到各个顶点的总权值
  92.     Dijkstra_minTree(G, 0, P, D);
  93.   
  94.     printf("最短路径为：\n");
  95.     for (int i = 1; i < G.vexnum; i++) {
  96.         printf("%d - %d的最短路径中的顶点有：", i, 0);
  97.         printf(" %d-", i);
  98.         int j = i;
  99.         //由于每一段最短路径上都记录着经过的顶点，所以采用嵌套的方式输出即可得到各个最短路径上的所有顶点
  100.         while (P[j] != 0) {
  101.             printf("%d-", P[j]);
  102.             j = P[j];
  103.         }
  104.         printf("0\n");
  105.     }
  106.     printf("源点到各顶点的最短路径长度为:\n");
  107.     for (int i = 1; i < G.vexnum; i++) {
  108.         printf("%d - %d : %d \n", G.vexs[0], G.vexs[i], D[i]);
  109.     }
  110.     return 0;
  111. }

迪杰斯特拉算法查找顶点 0 到其它顶点所有最短路径的 Java 程序为： 
  1. import java.util.Scanner;
  2.  
  3. public class Dijkstra {
  4.     static int V = 9; // 图中边的数量
  5.  
  6.     public static class MGraph {
  7.         int[] vexs = new int[V]; // 存储图中顶点数据
  8.         int[][] arcs = new int[V][V]; // 二维数组，记录顶点之间的关系
  9.         int vexnum, arcnum; // 记录图的顶点数和弧（边）数
  10.     }
  11.  
  12.     public static int LocateVex(MGraph G, int V) {
  13.         int i = 0;
  14.         // 遍历一维数组，找到变量v
  15.         for (; i < G.vexnum; i++) {
  16.             if (G.vexs[i] == V) {
  17.                 break;
  18.             }
  19.         }
  20.         // 如果找不到，输出提示语句，返回-1
  21.         if (i > G.vexnum) {
  22.             System.out.println("顶点输入有误");
  23.             return -1;
  24.         }
  25.         return i;
  26.     }
  27.  
  28.     // 构造无向有权图
  29.     public static void CreatDG(MGraph G) {
  30.         Scanner scn = new Scanner(System.in);
  31.         System.out.print("输入图的顶点数和边数：");
  32.         G.vexnum = scn.nextInt();
  33.         G.arcnum = scn.nextInt();
  34.         System.out.print("输入各个顶点：");
  35.         for (int i = 0; i < G.vexnum; i++) {
  36.             G.vexs[i] = scn.nextInt();
  37.         }
  38.         for (int i = 0; i < G.vexnum; i++) {
  39.             for (int j = 0; j < G.vexnum; j++) {
  40.                 G.arcs[i][j] = 65535;
  41.             }
  42.         }
  43.         System.out.println("输入各个边的数据:");
  44.         for (int i = 0; i < G.arcnum; i++) {
  45.             int v1 = scn.nextInt();
  46.             int v2 = scn.nextInt();
  47.             int w = scn.nextInt();
  48.  
  49.             int n = LocateVex(G, v1);
  50.             int m = LocateVex(G, v2);
  51.             if (m == -1 || n == -1) {
  52.                 return;
  53.             }
  54.             G.arcs[n][m] = w;
  55.             G.arcs[m][n] = w;
  56.         }
  57.     }
  58.  
  59.     // 迪杰斯特拉算法，v0表示有向网中起始点所在数组中的下标
  60.     public static void Dijkstra_minTree(MGraph G, int v0, int[] p, int[] D) {
  61.         int[] tab = new int[V]; // 为各个顶点配置一个标记值，用于确认该顶点是否已经找到最短路径
  62.         // 对各数组进行初始化
  63.         for (int v = 0; v < G.vexnum; v++) {
  64.             tab[v] = 0;
  65.             D[v] = G.arcs[v0][v];
  66.             p[v] = 0;
  67.         }
  68.         // 由于以v0位下标的顶点为起始点，所以不用再判断
  69.         D[v0] = 0;
  70.         tab[v0] = 1;
  71.         int k = 0;
  72.         for (int i = 0; i < G.vexnum; i++) {
  73.             int min = 65535;
  74.             // 选择到各顶点权值最小的顶点，即为本次能确定最短路径的顶点
  75.             for (int w = 0; w < G.vexnum; w++) {
  76.                 if (tab[w] != 1) {
  77.                     if (D[w] < min) {
  78.                         k = w;
  79.                         min = D[w];
  80.                     }
  81.                 }
  82.             }
  83.             // 设置该顶点的标志位为1，避免下次重复判断
  84.             tab[k] = 1;
  85.             // 对v0到各顶点的权值进行更新
  86.             for (int w = 0; w < G.vexnum; w++) {
  87.                 if (tab[w] != 1 && (min + G.arcs[k][w] < D[w])) {
  88.                     D[w] = min + G.arcs[k][w];
  89.                     p[w] = k;// 记录各个最短路径上存在的顶点
  90.                 }
  91.             }
  92.         }
  93.     }
  94.  
  95.     public static void main(String[] args) {
  96.         MGraph G = new MGraph();
  97.         CreatDG(G);
  98.         int[] P = new int[V]; // 记录顶点 0 到各个顶点的最短的路径
  99.         int[] D = new int[V]; // 记录顶点 0 到各个顶点的总权值
  100.         Dijkstra_minTree(G, 0, P, D);
  101.         System.out.println("最短路径为：");
  102.         for (int i = 1; i < G.vexnum; i++) {
  103.             System.out.print(i + " - " + 0 + " 的最短路径中的顶点有：");
  104.             System.out.print(i + "-");
  105.             int j = i;
  106.             // 由于每一段最短路径上都记录着经过的顶点，所以采用嵌套的方式输出即可得到各个最短路径上的所有顶点
  107.             while (P[j] != 0) {
  108.                 System.out.print(P[j] + "-");
  109.                 j = P[j];
  110.             }
  111.             System.out.println("0");
  112.         }
  113.         System.out.println("源点到各顶点的最短路径长度为:");
  114.         for (int i = 1; i < G.vexnum; i++) {
  115.             System.out.println(G.vexs[0] + " - " + G.vexs[i] + " : " + D[i]);
  116.         }
  117.     }
  118. }

迪杰斯特拉算法查找顶点 0 到其它顶点所有最短路径的 Python 程序为： 
  1. V = 20   #顶点的最大个数
  2. INFINITY = 65535    #设定一个最大值
  3. P = [0]*V  # 记录顶点 0 到各个顶点的最短的路径
  4. D = [0]*V  # 记录顶点 0 到各个顶点的总权值
  5.  
  6. class MGraph:
  7.     vexs = []*V   #存储图中顶点数据
  8.     arcs = [[0]*V for i in range(V)]    #二维列表，记录顶点之间的关系
  9.     vexnum = 0    #记录图的顶点数和弧（边）数
  10.     arcnum = 0
  11.  
  12. G = MGraph()
  13.  
  14. #根据顶点本身数据，判断出顶点在二维数组中的位置
  15. def LocateVex(G,v):
  16.     #遍历一维数组，找到变量v
  17.     for i in range(G.vexnum):
  18.         if G.vexs[i] == v:
  19.             break
  20.     #如果找不到，输出提示语句，返回-1
  21.     if i>G.vexnum:
  22.         print("顶点输入有误")
  23.         return -1
  24.     return i
  25.  
  26. #构造无向有权图
  27. def CreateDG(G):
  28.     print("输入图的顶点数和边数：",end='')
  29.     li = input().split()
  30.     G.vexnum = int(li[0])
  31.     G.arcnum = int(li[1])
  32.     print("输入各个顶点：",end='')
  33.     G.vexs = [int(i) for i in input().split()]
  34.     for i in range(G.vexnum):
  35.         for j in range(G.vexnum):
  36.             G.arcs[i][j] = INFINITY
  37.     print("输入各个边的数据:")
  38.     for i in range(G.arcnum):
  39.         li = input().split()
  40.         v1 = int(li[0])
  41.         v2 = int(li[1])
  42.         w = int(li[2])
  43.         n = LocateVex(G,v1)
  44.         m = LocateVex(G,v2)
  45.         if m == -1 or n == -1:
  46.             return
  47.         G.arcs[n][m] = w
  48.         G.arcs[m][n] = w
  49.  
  50. CreateDG(G)
  51. #迪杰斯特拉算法，v0表示有向网中起始点所在数组中的下标
  52. def Dijkstra_minTree(G,v0,P,D):
  53.     #为各个顶点配置一个标记值，用于确认该顶点是否已经找到最短路径
  54.     final = [0]*V
  55.     #对各数组进行初始化
  56.     for i in range(G.vexnum):
  57.         D[i] = G.arcs[v0][i]
  58.     #由于以v0位下标的顶点为起始点，所以不用再判断
  59.     D[v0] = 0
  60.     final[v0] = 1
  61.     k =0
  62.     for i in range(G.vexnum):
  63.         low = INFINITY
  64.         #选择到各顶点权值最小的顶点，即为本次能确定最短路径的顶点
  65.         for w in range(G.vexnum):
  66.             if not final[w]:
  67.                 if D[w] < low:
  68.                     k = w
  69.                     low = D[w]
  70.         #设置该顶点的标志位为1，避免下次重复判断
  71.         final[k] = 1
  72.         #对v0到各顶点的权值进行更新
  73.         for w in range(G.vexnum):
  74.             if not final[w] and (low + G.arcs[k][w]<D[w]):
  75.                 D[w] = low + G.arcs[k][w]
  76.                 P[w] = k   #记录各个最短路径上存在的顶点
  77.  
  78. Dijkstra_minTree(G,0,P,D)
  79.  
  80. print("最短路径为：")
  81. for i in range(1,G.vexnum):
  82.     print("%d - %d的最短路径中的顶点有："%(i,0),end='')
  83.     print("%d-"%(i),end='')
  84.     j = i
  85.     #由于每一段最短路径上都记录着经过的顶点，所以采用嵌套的方式输出即可得到各个最短路径上的所有顶点
  86.     while P[j] != 0:
  87.         print("%d-"%(P[j]),end='')
  88.         j = P[j]
  89.     print("0")
  90. print("源点到各顶点的最短路径长度为:")
  91. for i in range(1,G.vexnum):
  92.     print("%d - %d : %d"%(G.vexs[0], G.vexs[i], D[i]))

以上程序的执行过程为：

输入图的顶点数和边数：7 9
输入各个顶点：0 1 2 3 4 5 6
输入各个边的数据：
0 1 2
0 2 6
1 3 5
2 3 8
3 5 15
3 4 10
4 5 6
4 6 2
5 6 6
最短路径为：
1 - 0的最短路径中的顶点有： 1-0
2 - 0的最短路径中的顶点有： 2-0
3 - 0的最短路径中的顶点有： 3-1-0
4 - 0的最短路径中的顶点有： 4-3-1-0
5 - 0的最短路径中的顶点有： 5-3-1-0
6 - 0的最短路径中的顶点有： 6-4-3-1-0
源点到各顶点的最短路径长度为:
0 - 1 : 2
0 - 2 : 6
0 - 3 : 7
0 - 4 : 17
0 - 5 : 22
0 - 6 : 19

< 上一节下一节 >