迪杰斯特拉算法图文详解

迪杰斯特拉算法用于在无向加权图或者有向加权图中查找某个顶点到其他顶点的最短路径。

注意，迪杰斯特拉算法仅适用于在所有路径权值为非负数的图结构中寻找最小生成树。换句话说，只有图中各个路径（边）的权值为非负数时，迪杰斯特拉算法才能正确找到目标顶点到其它顶点的最短路径。

迪杰斯特拉算法的执行过程

我们以图 1 所示的无向加权图为例，讲解迪杰斯特拉算法的执行过程。

图 1 无向加权图

如果寻找顶点 0 到其它顶点的最短路径，迪杰斯特拉算法的实现过程为：

1) 初始状态下，顶点 0 到其他顶点的权值如下表所示：

表格中，∞ 表示无穷大。

 0-1 路径的权值最小，同样它也是从顶点 0 到顶点 1 的最短路径（如图 2 所示）。原因很简单，从顶点 0 出发共有 2 条路径， 0-2 的权值本就比 0-1 的权值大，因此从 0-2 出发是无法找到比 0-1 权值更小的路径的。

图 2 最短路径 0-1

2) 既然 0-1 为最短路径，我们用从顶点 1 到其它顶点的路径权值同表 1 记录的数据进行对比，从而找到从顶点 0 出发途径顶点 1 到达其它顶点的更短的路径（如表 2 所示）：

表中，绿色加粗的权值表示已确认为最短路径的权值，后续选择总权值最小的路径时不再进行选择；红色的权值为刚刚更新的权值。

可以看到，和先前 0-3 的权值为 ∞ 相比，0-1-3 的权值更小（2+5=7）。从表 2 中找出总权值最小的路径 0-2，它就是从顶点 0 到顶点 2 的最短路径（如图 3 所示）。

图 3 最短路径 0-2

3) 结合最短路径 0-2，利用从顶点 2 到其它顶点的权值更新表 2：

由于从顶点 2 出发，到顶点 3 的权值为 8，0-2-3 的总权值大于表格中记录的 0-1-3 的总权值，因此仍维持 0-1-3 的路径不变。从表 3 中找到总权值最小的路径 0-1-3（如图 4 所示），它就是从顶点 0 到顶点 3 的最短路径。

图 4 最短路径 0-1-3

4) 结合最短路径 0-1-3，利用从顶点 3 到其它顶点的权值更新表 3：

找到总权值最小的路径 0-1-3-4，它就是从顶点 0 到顶点 4 的最短路径（如图 5 所示）。

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

5) 结合 0-1-3-4，利用从顶点 4 到其它顶点的权值更新表 4：

找到总权值最小的路径 0-1-3-4-6，它就是从顶点 0 到顶点 6 的最短路径（如图 6 所示）。

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

6) 结合最短路径 0-1-3-4-6，根据从顶点 6 到其它顶点的权值更新表 5：

由于从顶点 6 到顶点 5 的总权值为 19+6 = 25，仍大于表 5 中记录的 22，因此舍弃该方案。找出表中总权值最小的路径 0-1-3-5，它就是从顶点 0 到顶点 5 的最短路径（如图 7 所示）。

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

由此，迪杰斯特拉算法就找出了顶点 0 到其它各个顶点的最短路径。

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

如下为实现迪杰斯特拉算法的 C 语言程序：

#include <stdio.h>
#define V 20                   //顶点的最大个数
#define INFINITY 65535
typedef struct {
    int vexs[V];         //存储图中顶点数据
    int arcs[V][V];      //二维数组，记录顶点之间的关系
    int vexnum, arcnum;  //记录图的顶点数和弧（边）数
}MGraph;

//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G, int v) {
    int i = 0;
    //遍历一维数组，找到变量v
    for (; i < G->vexnum; i++) {
        if (G->vexs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i > G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构造无向有权图
void CreateDG(MGraph *G) {
    printf("输入图的顶点数和边数：");
    scanf("%d %d", &(G->vexnum), &(G->arcnum));
    printf("输入各个顶点：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = INFINITY;
        }
    }
    printf("输入各个边的数据：\n");
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2, w;
        scanf("%d %d %d", &v1, &v2, &w);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (m == -1 || n == -1) {
            return;
        }
        G->arcs[n][m] = w;
        G->arcs[m][n] = w;
    }
}
//迪杰斯特拉算法，v0表示有向网中起始点所在数组中的下标
void Dijkstra_minTree(MGraph G, int v0, int p[V], int D[V]) {
    int final[V];//为各个顶点配置一个标记值，用于确认该顶点是否已经找到最短路径
    //对各数组进行初始化
    for (int v = 0; v < G.vexnum; v++) {
        final[v] = 0;
        D[v] = G.arcs[v0][v];
        p[v] = 0;
    }
    //由于以v0位下标的顶点为起始点，所以不用再判断
    D[v0] = 0;
    final[v0] = 1;
    int k = 0;
    for (int i = 0; i < G.vexnum; i++) {
        int min = INFINITY;
        //选择到各顶点权值最小的顶点，即为本次能确定最短路径的顶点
        for (int w = 0; w < G.vexnum; w++) {
            if (!final[w]) {
                if (D[w] < min) {
                    k = w;
                    min = D[w];
                }
            }
        }
        //设置该顶点的标志位为1，避免下次重复判断
        final[k] = 1;
        //对v0到各顶点的权值进行更新
        for (int w = 0; w < G.vexnum; w++) {
            if (!final[w] && (min + G.arcs[k][w] < D[w])) {
                D[w] = min + G.arcs[k][w];
                p[w] = k;//记录各个最短路径上存在的顶点
            }
        }
    }
}
int main() {
    MGraph G;
    CreateDG(&G);
    int P[V] = { 0 };   // 记录顶点 0 到各个顶点的最短的路径
    int D[V] = { 0 };   // 记录顶点 0 到各个顶点的总权值
    Dijkstra_minTree(G, 0, P, D);
   
    printf("最短路径为：\n");
    for (int i = 1; i < G.vexnum; i++) {
        printf("%d - %d的最短路径中的顶点有：", i, 0);
        printf(" %d-", i);
        int j = i;
        //由于每一段最短路径上都记录着经过的顶点，所以采用嵌套的方式输出即可得到各个最短路径上的所有顶点
        while (P[j] != 0) {
            printf("%d-", P[j]);
            j = P[j];
        }
        printf("0\n");
    }
    printf("源点到各顶点的最短路径长度为:\n");
    for (int i = 1; i < G.vexnum; i++) {
        printf("%d - %d : %d \n", G.vexs[0], G.vexs[i], D[i]);
    }
    return 0;
}

如下为实现迪杰斯特拉算法的 Java 程序：

import java.util.Scanner;

public class Dijkstra {
    static int V = 9; // 图中边的数量

    public static class MGraph {
        int[] vexs = new int[V]; // 存储图中顶点数据
        int[][] arcs = new int[V][V]; // 二维数组，记录顶点之间的关系
        int vexnum, arcnum; // 记录图的顶点数和弧（边）数
    }

    public static int LocateVex(MGraph G, int V) {
        int i = 0;
        // 遍历一维数组，找到变量v
        for (; i < G.vexnum; i++) {
            if (G.vexs[i] == V) {
                break;
            }
        }
        // 如果找不到，输出提示语句，返回-1
        if (i > G.vexnum) {
            System.out.println("顶点输入有误");
            return -1;
        }
        return i;
    }

    // 构造无向有权图
    public static void CreatDG(MGraph G) {
        Scanner scn = new Scanner(System.in);
        System.out.print("输入图的顶点数和边数：");
        G.vexnum = scn.nextInt();
        G.arcnum = scn.nextInt();
        System.out.print("输入各个顶点：");
        for (int i = 0; i < G.vexnum; i++) {
            G.vexs[i] = scn.nextInt();
        }
        for (int i = 0; i < G.vexnum; i++) {
            for (int j = 0; j < G.vexnum; j++) {
                G.arcs[i][j] = 65535;
            }
        }
        System.out.println("输入各个边的数据:");
        for (int i = 0; i < G.arcnum; i++) {
            int v1 = scn.nextInt();
            int v2 = scn.nextInt();
            int w = scn.nextInt();

            int n = LocateVex(G, v1);
            int m = LocateVex(G, v2);
            if (m == -1 || n == -1) {
                return;
            }
            G.arcs[n][m] = w;
            G.arcs[m][n] = w;
        }

    }

    // 迪杰斯特拉算法，v0表示有向网中起始点所在数组中的下标
    public static void Dijkstra_minTree(MGraph G, int v0, int[] p, int[] D) {
        int[] tab = new int[V]; // 为各个顶点配置一个标记值，用于确认该顶点是否已经找到最短路径
        // 对各数组进行初始化
        for (int v = 0; v < G.vexnum; v++) {
            tab[v] = 0;
            D[v] = G.arcs[v0][v];
            p[v] = 0;
        }
        // 由于以v0位下标的顶点为起始点，所以不用再判断
        D[v0] = 0;
        tab[v0] = 1;
        int k = 0;
        for (int i = 0; i < G.vexnum; i++) {
            int min = 65535;
            // 选择到各顶点权值最小的顶点，即为本次能确定最短路径的顶点
            for (int w = 0; w < G.vexnum; w++) {
                if (tab[w] != 1) {
                    if (D[w] < min) {
                        k = w;
                        min = D[w];
                    }
                }
            }
            // 设置该顶点的标志位为1，避免下次重复判断
            tab[k] = 1;
            // 对v0到各顶点的权值进行更新
            for (int w = 0; w < G.vexnum; w++) {
                if (tab[w] != 1 && (min + G.arcs[k][w] < D[w])) {
                    D[w] = min + G.arcs[k][w];
                    p[w] = k;// 记录各个最短路径上存在的顶点
                }
            }
        }
    }

    public static void main(String[] args) {
        MGraph G = new MGraph();
        CreatDG(G);
        int[] P = new int[V]; // 记录顶点 0 到各个顶点的最短的路径
        int[] D = new int[V]; // 记录顶点 0 到各个顶点的总权值
        Dijkstra_minTree(G, 0, P, D);
        System.out.println("最短路径为：");
        for (int i = 1; i < G.vexnum; i++) {
            System.out.print(i + " - " + 0 + " 的最短路径中的顶点有：");
            System.out.print(i + "-");
            int j = i;
            // 由于每一段最短路径上都记录着经过的顶点，所以采用嵌套的方式输出即可得到各个最短路径上的所有顶点
            while (P[j] != 0) {
                System.out.print(P[j] + "-");
                j = P[j];
            }
            System.out.println("0");
        }
        System.out.println("源点到各顶点的最短路径长度为:");
        for (int i = 1; i < G.vexnum; i++) {
            System.out.println(G.vexs[0] + " - " + G.vexs[i] + " : " + D[i]);
        }
    }
}

如下为实现迪杰斯特拉算法的 Python 程序：

V = 20   #顶点的最大个数
INFINITY = 65535    #设定一个最大值
P = [0]*V  # 记录顶点 0 到各个顶点的最短的路径
D = [0]*V  # 记录顶点 0 到各个顶点的总权值

class MGraph:
    vexs = []*V   #存储图中顶点数据
    arcs = [[0]*V for i in range(V)]    #二维列表，记录顶点之间的关系
    vexnum = 0    #记录图的顶点数和弧（边）数
    arcnum = 0

G = MGraph()

#根据顶点本身数据，判断出顶点在二维数组中的位置
def LocateVex(G,v):
    #遍历一维数组，找到变量v
    for i in range(G.vexnum):
        if G.vexs[i] == v:
            break
    #如果找不到，输出提示语句，返回-1
    if i>G.vexnum:
        print("顶点输入有误")
        return -1
    return i

#构造无向有权图
def CreateDG(G):
    print("输入图的顶点数和边数：",end='')
    li = input().split()
    G.vexnum = int(li[0])
    G.arcnum = int(li[1])
    print("输入各个顶点：",end='')
    G.vexs = [int(i) for i in input().split()]
    for i in range(G.vexnum):
        for j in range(G.vexnum):
            G.arcs[i][j] = INFINITY
    print("输入各个边的数据:")
    for i in range(G.arcnum):
        li = input().split()
        v1 = int(li[0])
        v2 = int(li[1])
        w = int(li[2])
        n = LocateVex(G,v1)
        m = LocateVex(G,v2)
        if m == -1 or n == -1:
            return
        G.arcs[n][m] = w
        G.arcs[m][n] = w

CreateDG(G)
#迪杰斯特拉算法，v0表示有向网中起始点所在数组中的下标
def Dijkstra_minTree(G,v0,P,D):
    #为各个顶点配置一个标记值，用于确认该顶点是否已经找到最短路径
    final = [0]*V
    #对各数组进行初始化
    for i in range(G.vexnum):
        D[i] = G.arcs[v0][i]
    #由于以v0位下标的顶点为起始点，所以不用再判断
    D[v0] = 0
    final[v0] = 1
    k =0
    for i in range(G.vexnum):
        low = INFINITY
        #选择到各顶点权值最小的顶点，即为本次能确定最短路径的顶点
        for w in range(G.vexnum):
            if not final[w]:
                if D[w] < low:
                    k = w
                    low = D[w]
        #设置该顶点的标志位为1，避免下次重复判断
        final[k] = 1
        #对v0到各顶点的权值进行更新
        for w in range(G.vexnum):
            if not final[w] and (low + G.arcs[k][w]<D[w]):
                D[w] = low + G.arcs[k][w]
                P[w] = k   #记录各个最短路径上存在的顶点

Dijkstra_minTree(G,0,P,D)

print("最短路径为：")
for i in range(1,G.vexnum):
    print("%d - %d的最短路径中的顶点有："%(i,0),end='')
    print("%d-"%(i),end='')
    j = i
    #由于每一段最短路径上都记录着经过的顶点，所以采用嵌套的方式输出即可得到各个最短路径上的所有顶点
    while P[j] != 0:
        print("%d-"%(P[j]),end='')
        j = P[j]
    print("0")
print("源点到各顶点的最短路径长度为:")
for i in range(1,G.vexnum):
    print("%d - %d : %d"%(G.vexs[0], G.vexs[i], D[i]))

以图 1 所示的图为例，利用上述程序查找顶点 0 到其它顶点的最短路径，输出结果为：

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
V0 - V1的最短路径中的顶点有(逆序)： V1 V0
V0 - V2的最短路径中的顶点有(逆序)： V2 V0
V0 - V3的最短路径中的顶点有(逆序)： V3 V1 V0
V0 - V4的最短路径中的顶点有(逆序)： V4 V3 V1 V0
V0 - V5的最短路径中的顶点有(逆序)： V5 V3 V1 V0
V0 - V6的最短路径中的顶点有(逆序)： V6 V4 V3 V1 V0
源点到各顶点的最短路径长度为:
V0 - V1 : 2
V0 - V2 : 6
V0 - V3 : 7
V0 - V4 : 17
V0 - V5 : 22
V0 - V6 : 19