狄克斯特拉（Dijkstra）算法

2023-01-27 19:37:21

引入

从A点到B点的最短路径是什么？求最短路径的两种算法：Dijkstra算法和Floyd算法。

网图：带权图。

非网图最短路径：两顶点间经过的边数最少的路径。（非网图也可被理解为各边权值为1的网图。）

网图最短路径：两顶点间经过的边上权值之和最少的路径。路径上第一个顶点是源点，最后的顶点是终点。

问题：下图中V₀ 点到其余各个顶点V_k的最短路径是什么？

演示

设图G中的每个顶点为V₀到该点的路径。并用以下形式来表示：

Path[x].Length：V₀到该路径所处终点的V[x]的最短路径。如Path[2].Length为V₀->V₂的最短路径。

Path[x].Predecessor：V₀到该路径所处终点的上一个顶点的编号（下标）。如Path[2].Predecessor为0，表示V₀->V₂的最短路径，顶点V₂的前一个顶点为V₁，即经过V₁然后到达V₂。

Path[x].IsVisited：顶点Vx是否曾作为立足点来查找接下来的最短路径。其中V_x是V₀到该路径所处的终点。

G[i][j]：用邻接矩阵表示图G。G[i][j]为顶点V_i到顶点V_j的权值。

0.初始化：
所有路径的Predecessor设为-1，Length设为0，IsVisited设为false。
从源点开始Path[0].Predecessor = 0，因为V₀->V₀路径上的一个顶点为V₀，V₀->V₀的距离为0，故Path[0].Length = 0。

步骤0：

1.以V₀为立足点，所以Path[0].IsVisited = true。
2.V₀与V₀、V₁及V₂相连。
Path[0].IsVisited为true，故跳过这个路径。

Path[0].Length + G[0][1] = 0 + 1 < Path[2].Length = ∞故Path[1].Length = 1，Path[1].Predecessor = 0；

Path[0].Length + G[0][2] = 0 + 5 < Path[2].Length = ∞故Path[2].Length = 5，Path[2].Predecessor = 0；

3.现查找图G中所有9个路径（每个顶点皆构成一个最短路径）中未曾作为立足点且路径最短的哪个路径的终点作为新的立足点。
Path[0].IsVisited为true，故跳过。而其余的为false。
Path[1].Length为1，Path[2].Length为5，其余Path.Length为∞。故选Path[1]的终点V1作为新的立足点。令V₀ = 1，从顶点V₁开始下一轮寻找。

步骤1：

1.以V₁为立足点，所以Path[1].IsVisited = true。
2.V₁与V₀、V₁、V₂、V₃及V₄相连。
Path[0].IsVisited为true，Path[1].IsVisited为true，故跳过这些路径。

Path[1].Length + G[1][2] = 1 + 3 < Path[2].Length = 5故Path[2].Length = 4，Path[2].Predecessor = 1；

Path[1].Length + G[1][3] = 1 + 7 < Path[3].Length = ∞故Path[3].Length = 8，Path[3].Predecessor = 1；

Path[1].Length + G[1][4] = 1 + 5 < Path[4].Length = ∞故Path[4].Length = 6，Path[4].Predecessor = 1；

3.现查找图G中所有9个路径（每个顶点皆构成一个最短路径）中未曾作为立足点且路径最短的哪个路径的终点作为新的立足点。
Path[0、1].IsVisited为true，故跳过。而其余的为false。
Path[2].Length为4，Path[3].Length为8，Path[4].Length为6，其余Path.Length为∞。故选Path[2]的终点V2作为新的立足点。令V₀ = 2，从顶点V2开始下一轮寻找。

步骤2：

1.以V₂为立足点，所以Path[2].IsVisited = true。
2.V₂与V₀、V₁、V₂、V₄、及V₅相连。
Path[0、1、2].IsVisited为true，故跳过这些路径。

Path[2].Length + G[2][4] = 4 + 1 < Path[4].Length = 6故Path[4].Length = 5，Path[4].Predecessor = 2；

Path[2].Length + G[2][5] = 4 + 7 < Path[5].Length = ∞故Path[5].Length = 11，Path[5].Predecessor = 2；

3.现查找图G中所有9个路径（每个顶点皆构成一个最短路径）中未曾作为立足点且路径最短的哪个路径的终点作为新的立足点。
Path[0、1、2].IsVisited为true，故跳过。而其余的为false。
Path[3].Length为8，Path[4].Length为5，Path[5].Length为11，其余Path.Length为∞。故选Path[4]的终点V₄作为新的立足点。令V₀ = 4，从顶点V4开始下一轮寻找。

步骤3：

1.以V₄为立足点，所以Path[4].IsVisited = true。
2.V₄与V₁、V₂、V₃、V₄、V₅、V₆及V₇相连。
Path[0、1、2、4].IsVisited为true，故跳过这些路径。

Path[4].Length + G[4][3] = 5 + 2 < Path[3].Length = 8故Path[3].Length = 7，Path[3].Predecessor = 4；

Path[4].Length + G[4][5] = 5 + 3 < Path[5].Length = 11故Path[5].Length = 8，Path[5].Predecessor = 4；

Path[4].Length + G[4][6] = 5 + 6 < Path[6].Length = ∞故Path[6].Length = 11，Path[6].Predecessor = 4；

Path[4].Length + G[4][7] = 5 + 9 < Path[7].Length = ∞故Path[7].Length = 14，Path[6].Predecessor = 4；

3.现查找图G中所有9个路径（每个顶点皆构成一个最短路径）中未曾作为立足点且路径最短的哪个路径的终点作为新的立足点。
Path[0、1、2、4].IsVisited为true，故跳过。而其余的为false。
Path[3].Length为7，Path[5].Length为8，Path[6].Length为11，Path[7].Length为14，其余Path.Length为∞。故选Path[3]的终点V₃作为新的立足点。令V₀=3，从顶点V3开始下一轮寻找。

步骤4：

1.以V₃为立足点，所以Path[3].IsVisited = true。
2.V₃与V₁、V₄及V₆相连。
Path[0、1、2、3、4].IsVisited为true，故跳过这些路径。

Path[3].Length + G[3][6] = 7 + 3 < Path[6].Length = 11故Path[6].Length = 10，Path[6].Predecessor = 3；

3.现查找图G中所有9个路径（每个顶点皆构成一个最短路径）中未曾作为立足点且路径最短的哪个路径的终点作为新的立足点。
Path[0、1、2、3、4].IsVisited为true，故跳过。而其余的为false。
Path[5].Length为8，Path[6].Length为10，Path[7].Length为14，其余Path.Length为∞。故选Path[5]的终点V5作为新的立足点。令V₀ = 5，从顶点V5开始下一轮寻找。

步骤5：

1.以V₅为立足点，所以Path[5].IsVisited = true。
2.V₅与V₂、V₄、V₅及V₇相连。
Path[0、1、2、3、4、5].IsVisited为true，故跳过这些路径。

Path[5].Length + G[5][7] = 8 + 5 < Path[7].Length = 14故Path[7].Length = 13，Path[7].Predecessor = 5；

3.现查找图G中所有9个路径（每个顶点皆构成一个最短路径）中未曾作为立足点且路径最短的哪个路径的终点作为新的立足点。
Path[0、1、2、3、4、5].IsVisited为true，故跳过。而其余的为false。
Path[6].Length为10，Path[7].Length为13，其余Path.Length为∞。故选Path[6]的终点V6作为新的立足点。令V₀ = 6，从顶点V₆开始下一轮寻找。

步骤6：

1.以V₆为立足点，所以Path[6].IsVisited = true。
2.V₆与V₃、V₄、V₇及V₈相连。
Path[0、1、2、3、4、5、6].IsVisited为true，故跳过这些路径。

Path[6].Length + G[6][7] = 10 + 2 < Path[7].Length = 13故Path[7].Length = 12，Path[7].Predecessor = 6；

Path[6].Length + G[6][8] = 10 + 7 < Path[8].Length = ∞故Path[8].Length = 17，Path[8].Predecessor = 6；

3.现查找图G中所有9个路径（每个顶点皆构成一个最短路径）中未曾作为立足点且路径最短的哪个路径的终点作为新的立足点。
Path[0、1、2、3、4、5、6].IsVisited为true，故跳过。而其余的为false。
Path[7].Length为12，Path[8].Length为17，没有其余Path了。故选Path[7]的终点V7作为新的立足点。令V₀ = 7，从顶点V7开始下一轮寻找。

步骤7：

1.以V_{7_{为立足点，所以Path[7].IsVisited = true。

2.V₇与V₄、V₅、V₆、V₇及V₈相连。

Path[0、1、2、3、4、5、6、7].IsVisited为true，故跳过这些路径。}}

Path[7].Length + G[7][8] = 12 + 4<Path[8].Length = 17故Path[8].Length = 16，Path[8].Predecessor = 7；

3.现查找图G中所有9个路径（每个顶点皆构成一个最短路径）中未曾作为立足点且路径最短的哪个路径的终点作为新的立足点。
Path[0、1、2、3、4、5、6、7].IsVisited为true，故跳过。而其余的为false。
Path[8].Length为16，无其余Path。故选Path[8]的终点V8作为新的立足点。令V₀ = 8，从顶点V8开始下一轮寻找。

步骤8：

1.以V₈为立足点，所以Path[8].IsVisited = true。
2.V₈与V₆、V₇及V₈相连。
Path[0、1、2、3、4、5、6、7、8].IsVisited为true，故跳过这些路径。

已无没有探索过的路径了。

3.现查找图G中所有9个路径（每个顶点皆构成一个最短路径）中未曾作为立足点且路径最短的哪个路径的终点作为新的立足点。
Path[0、1、2、3、4、5、6、7、8].IsVisited为true，故跳过。已无没有探索过的路径了。无需开始下一轮的寻找。

完成探索，Path数组即是V₀到各顶点的最短路径。输出Path数组即可。
步骤0~8中的操作都是重复的，总结形成代码。

伪代码

Dijkstra(Graph g, int v, int n)
{
    // 0. 初始化。
    Path[] paths = new Path[n];

    // 将每个路径设为初始值。
    for (int i = 0; i < n; i++)
    {
        paths[i].Length = ∞;
        paths[i].Predecessor = -1;
        paths[i].IsVisited = false;
    }

    // 以v为源点寻找最短路径。
    int k = v;
    // v0->v0的路径长度为0。
    paths[k].Length = 0;
    // v0->v0路径的上一个顶点为v0。
    paths[k].Predecessor = 0;

    // 逐个顶点探索最短路径。
    for (int i = 0; i < n; i++)
    {
        // 1.以vk为立足点寻找它到其余顶点的最短路径。
        paths[k].IsVisited = true;
        // 2.探索vk的最短路径
        for (int j = 0; j < n; j++)
        {
            // vj未曾作为立足点 &&
            // 存在边(vk, vj) &&
            // vk到vj的当前路径长度比已经探索到的源点到vj的路径还更短。
            if (paths[j].IsVisited = false &&
                g[k][j] != ∞ &&
                paths[k].Length + g[k][j] < paths[j].Length)
            {
                // 更新源点到vj的路径（paths[k]是源点到vk的最短路径）。
                paths[j].Length = paths[k].Length + g[k][j];
                // 路径j的上一个顶点应该更新为k（即源点到vj是经过vk到达vj的）。
                paths[j].Predecessor = k;
            }
        }

        // 3.寻找图G中已知的最短路径。并以该路径的终点为新的立足点探索最短路径。
        // 设当前最小值为无穷。
        int min = ∞;
        // 遍历所有路径。
        for (int j = 0; j < n; j++)
        {
            // 路径的终点曾作为立足点的路径，其已是最短路径。
            // 该路径的终点无需再作为立足点去探索最短路径。
            // 故，直接跳过。
            if (paths[j].IsVisited == true)
            {
                continue;
            }

            if (paths[j].Length < min)
            {
                min = paths[j].Length;
                k = j;
            }
        }

        // 此时k即是新的最短路径的下标。
    }

    // 输出paths，每条路径皆为源点到该路径的终点的最短路径。
}

分析

Dijkstra算法解决了从某源点到其余各点的最短路径问题。从循环嵌套可知算法的时间复杂度为O(n2)。（摘自《大话数据结构》。）

最小生成树与最小路径的区别

最小生成树：将图G中所有顶点相连所用的路程最短（所有路径之和最小）。保证图中的所有路径之和最短。但某个点到另一个点是否最近，不能保证。

最小路径：从图G某各顶点出发，到其它顶点所用路程最短。保证某个点到其余点路程最短，但把所有点连接起来是否路程最短，就不一定了。

例如：下面这幅图的最小生成树和最小路径。

代码

用邻接矩阵来表示图G。如下：

C#代码

using System;

namespace Dijkstra
{
    class Program
    {
        static void Main(string[] args)
        {
            int numberOfVertexes = 9,
                infinity = Constants.Infinity;

            int[][] graph = new int[][] {
                new int[]{0, 1, 5, infinity, infinity, infinity, infinity, infinity, infinity },
                new int[]{ 1, 0, 3, 7, 5, infinity, infinity, infinity, infinity },
                new int[]{ 5, 3, 0, infinity, 1, 7, infinity, infinity, infinity },
                new int[]{ infinity, 7, infinity, 0, 2, infinity, 3, infinity, infinity },
                new int[]{ infinity, 5, 1, 2, 0, 3, 6, 9, infinity },
                new int[]{ infinity, infinity, 7, infinity, 3, 0, infinity, 5, infinity },
                new int[]{ infinity, infinity, infinity, 3, 6, infinity, 0, 2, 7 },
                new int[]{ infinity, infinity, infinity, infinity, 9, 5, 2, 0, 4 },
                new int[]{ infinity, infinity, infinity, infinity, infinity, infinity, 7, 4, 0 },
            };

            Dijkstra(graph, 0, numberOfVertexes);
        }

        /// <summary>
        /// 源点到图中各顶点的最短路径。
        /// </summary>
        /// <param name="graph">图G。</param>
        /// <param name="initialVertex">源点（图G中顶点的下标），图中任意顶点都可以是源点。</param>
        /// <param name="numberOfVertexes">图G中顶点的数目。</param>
        static void Dijkstra(int[][] graph, int initialVertex, int numberOfVertexes)
        {
            /** 
             * 源点到以数组paths的下标为下标的顶点的最短路径
             * 的长度（或权重累加和）。
             * 比如：paths[2]，表示源点到顶点v2的最短路径。
             */
            // 0.初始化
            Path[] paths = new Path[numberOfVertexes];

            /**
             * 每条路径设为初始值。
             */
            for (int i = 0; i < numberOfVertexes; i++)
            {
                paths[i] = new Path()
                {
                    Length = Constants.Infinity,
                    Predecessor = -1,
                    IsVisited = false
                };
            }

            int k = initialVertex;               // 从源点开始寻找最短路径。
            paths[k].Length = 0;                 // 源点->源点的路径为0。
            paths[k].Predecessor = k;            // 源点->源点的路径的前驱（上一个）顶点就是源点。如：(v1, v1)。

            /**
             * 图G有n个顶点。需要以图中各顶点作为最短路径的立足
             * 点探索最短路径。
             */
            // 逐个顶点探索最短路径。
            for (int i = 0; i < numberOfVertexes; i++)
            {
                paths[k].IsVisited = true;       // 1.以Vk为立足点探索它到其余顶点的最短路径。

                /**
                * 2.探索Vk的最短路径。从Vk到其余各与Vk相关联的顶点。
                */
                for (int j = 0; j < numberOfVertexes; j++)
                {
                    /**
                     * 若
                     * 1.paths[j]对应的终点未曾作为立足点。（Vj未曾作为立足点。）
                     * 2.存在边(Vk, Vj)。
                     * 3.当前最短路径paths[k]的终点Vk到Vj的路径比已经探索到的源点到Vj的路径paths[j]还更短。
                     * 则需要更新paths[j]，即发现路一条到vj的新路径且比已知长度更短。
                     */
                    if (paths[j].IsVisited == false &&
                        graph[k][j] != Constants.Infinity &&
                        (paths[k].Length + graph[k][j] < paths[j].Length))
                    {
                        // 更新源点到vj的路径（paths[k]是源点到vk的最短路径)。
                        paths[j].Length = paths[k].Length + graph[k][j];
                        // 路径j的上一个顶点应该更新为k（即源点到vj是经过vk到达vj的）。
                        paths[j].Predecessor = k;
                    }
                }

                /**
                 * 3.寻找图G中已知的最短路径。并以该路径的终点为新的立足点探索最短路径。
                 * 新立足点Vk，其需满足以下条件：
                 * 1.未曾作为立足点，即paths[k].IsVisited为false。
                 * 2.路径最小，即paths[k].Length为Min(paths[0].Length, ..., paths[n-1].Length)
                */
                int min = Constants.Infinity;    // 设当前最小值为无穷。
                for (int j = 0; j < numberOfVertexes; j++)
                {
                    if (paths[j].IsVisited)      // 若曾作为立足点，则跳过并转向下一个。
                        continue;
                    if (paths[j].Length < min)   // 发现更小的路径：
                    {
                        k = j;                   // 记录下顶点下标（编号）。
                        min = paths[j].Length;   // 记录下最小路径。
                    }
                }                                // 在paths[k]处找到最小路径。
            }

            // 输出结果
            PrintResult(paths, initialVertex);
        }

        static void DijkstraSimplified(int[][] graph, int initialVertex, int numberOfVertexes)
        {
            /** 
             * 源点到以数组paths的下标为下标的顶点的最短路径
             * 的长度（或权重累加和）。
             * 比如：paths[2]，表示源点到顶点v2的最短路径。
             */
            // 0.初始化（转换为数组，而不用类。）
            //int[] paths = new int[numberOfVertexes];
            int[] lengths = new int[numberOfVertexes];
            int[] predecessors = new int[numberOfVertexes];
            bool[] isVisiteds = new bool[numberOfVertexes];

            //Path[] paths = new Path[numberOfVertexes];

            /**
             * 每条路径设为初始值。
             */
            for (int i = 0; i < numberOfVertexes; i++)
            {
                lengths[i] = Constants.Infinity;
                predecessors[i] = -1;
                isVisiteds[i] = false;
                
            }

            int k = initialVertex;               // 从源点开始寻找最短路径。
            lengths[k] = 0;                      // 源点->源点的路径为0。
            predecessors[k] = k;                 // 源点->源点的路径的前驱（上一个）顶点就是源点。如：(v1, v1)。

            /**
             * 图G有n个顶点。需要以图中各顶点作为最短路径的立足
             * 点探索最短路径。
             */
            // 逐个顶点探索最短路径。
            for (int i = 0; i < numberOfVertexes; i++)
            {
                // 1.以Vk为立足点探索它到其余顶点的最短路径。
                isVisiteds[k] = true;

                /**
                * 2.探索Vk的最短路径。从Vk到其余各与Vk相关联的顶点。
                */
                for (int j = 0; j < numberOfVertexes; j++)
                {
                    /**
                     * 若
                     * 1.paths[j]对应的终点未曾作为立足点。（Vj未曾作为立足点。）
                     * 2.存在边(Vk, Vj)。
                     * 3.当前最短路径paths[k]的终点Vk到Vj的路径比已经探索到的源点到Vj的路径paths[j]还更短。
                     * 则需要更新paths[j]，即发现路一条到vj的新路径且比已知长度更短。
                     */
                    if (isVisiteds[j] == false &&
                        graph[k][j] != Constants.Infinity &&
                        (lengths[k] + graph[k][j] < lengths[j]))
                    {
                        // 更新源点到vj的路径（paths[k]是源点到vk的最短路径)。
                        lengths[j] = lengths[k] + graph[k][j];
                        // 路径j的上一个顶点应该更新为k（即源点到vj是经过vk到达vj的）。
                        predecessors[j] = k;
                    }
                }

                /**
                 * 3.寻找图G中已知的最短路径。并以该路径的终点为新的立足点探索最短路径。
                 * 新立足点Vk，其需满足以下条件：
                 * 1.未曾作为立足点，即paths[k].IsVisited为false。
                 * 2.路径最小，即paths[k].Length为Min(paths[0].Length, ..., paths[n-1].Length)
                */
                int min = Constants.Infinity;    // 设当前最小值为无穷。
                for (int j = 0; j < numberOfVertexes; j++)
                {
                    if (isVisiteds[j])           // 若曾作为立足点，则跳过并转向下一个。
                        continue;
                    if (lengths[j] < min)        // 发现更小的路径：
                    {
                        k = j;                   // 记录下顶点下标（编号）。
                        min = lengths[j];        // 记录下最小路径。
                    }
                }                                // 在paths[k]处找到最小路径。
            }

            // 输出结果
            for (int i = 0; i < numberOfVertexes; i++)
            {
                string result = $"";
                int cursor = i;

                if (cursor == initialVertex)
                {
                    result = $"->{cursor}";
                }

                while (cursor != initialVertex)
                {
                    result = $"->{cursor}{result}";
                    cursor = predecessors[cursor];
                }
                result = $"{cursor}{result}: {lengths[i]}";
                Console.WriteLine(result);
            }
        }

        static void PrintResult(Path[] paths, int initialVertex)
        {
            int numberOfVertexes = paths.Length;

            for (int i = 0; i < numberOfVertexes; i++)
            {
                string result = $"";
                int cursor = i;

                if (cursor == initialVertex)
                {
                    result = $"->{cursor}";
                }

                while (cursor != initialVertex)
                {
                    result = $"->{cursor}{result}";
                    cursor = paths[cursor].Predecessor;
                }
                result = $"{cursor}{result}: {paths[i].Length}";
                Console.WriteLine(result);
            }
        }

        static void PrintArray(int[] array)
        {
            Console.Write("[ ");
            for (int i = 0; i < array.Length - 1; i++)  // 输出数组的前面n-1个
            {
                Console.Write($"{ToInfinity(array[i])}, ");
            }
            if (array.Length > 0)                       // 输出数组的最后1个
            {
                int n = array.Length - 1;
                Console.Write($"{ToInfinity(array[n])}");
            }
            Console.WriteLine(" ]");
        }

        static string ToInfinity(int i) => i == int.MaxValue ? "∞" : i.ToString();
    }

    /**
     * 路径类。源点到图中其余顶点vk的最短路径。
     */
    public class Path
    {
        // 源点到顶点vk的路径长度。（途径的各边的权值之和。该值最终即是最短路径长度。）
        public int Length { get; set; } = Constants.Infinity;
        // 路径终点途经的上一个顶点（的下标）。
        public int Predecessor { get; set; } = -1;
        // 路径终点是否曾作为立足点。
        public bool IsVisited { get; set; } = false;
    }

    /**
     * 表示常量的类。
     */
    public static class Constants
    {
        public static int Infinity { get => int.MaxValue; }
    }
}

/**
运行结果：
0->0: 0
0->1: 1
0->1->2: 4
0->1->2->4->3: 7
0->1->2->4: 5
0->1->2->4->5: 8
0->1->2->4->3->6: 10
0->1->2->4->3->6->7: 12
0->1->2->4->3->6->7->8: 16
 */

TypeScript代码

const infinity: number = Number.MAX_VALUE;

/**
 * 路径类。源点到图中其余顶点vk的最短路径。
 */
class Path {
    // 源点到顶点vk的路径长度。（途径的各边的权值之和。该值最终即是最短路径长度。）
    Length: number = 0;
    // 路径终点途经的上一个顶点（的下标）。
    Predecessor: number = -1;
    // 路径终点是否曾作为立足点。
    IsVisited: boolean = false;
}

/**
 * 源点到图中各顶点的最短路径。
 * @param graph 图G。
 * @param initialVertex 源点（图G中顶点的下标），图中任意顶点都可以是源点。
 * @param numberOfVertexes 图G中顶点的数目。
 * @author kokiafan 
 */
function dijkstra(graph: number[][], initialVertex: number, numberOfVertexes: number): void {
    /** 
     * 源点到以数组paths的下标为下标的顶点的最短路径
     * 的长度（或权重累加和）。
     * 比如：paths[2]，表示源点到顶点v2的最短路径。
     */
    // 0.初始化
    let paths: Path[] = [];

    /**
     * 每条路径设为初始值。
     */
    for (let i = 0; i < numberOfVertexes; i++) {
        paths[i] = new Path();
        paths[i].Length = infinity;
        paths[i].Predecessor = -1;
        paths[i].IsVisited = false;
    }

    let k: number = initialVertex;     // 从源点开始寻找最短路径。
    paths[k].Length = 0;               // 源点->源点的路径为0。
    paths[k].Predecessor = k;          // 源点->源点的路径的前驱（上一个）顶点就是源点。如：(v1, v1)。
    /**
     * 图G有n个顶点。需要以图中各顶点作为最短路径的立足
     * 点探索最短路径。
     */
    // 逐个顶点探索最短路径。
    for (let i = 0; i < numberOfVertexes; i++) {
        // 1.以Vk为立足点探索它到其余顶点的最短路径。
        paths[k].IsVisited = true;

        /**
        * 2.探索Vk的最短路径。从Vk到其余各与Vk相关联的顶点。
        */
        for (let j = 0; j < numberOfVertexes; j++) {
            /**
             * 若
             * 1.paths[j]对应的终点未曾作为立足点。（Vj未曾作为立足点。）
             * 2.存在边(Vk, Vj)。
             * 3.当前最短路径paths[k]的终点Vk到Vj的路径比已经探索到的源点到Vj的路径paths[j]还更短。
             * 则需要更新paths[j]，即发现路一条到vj的新路径且比已知长度更短。
             */
            if (paths[j].IsVisited == false &&
                graph[k][j] != infinity &&
                (paths[k].Length + graph[k][j] < paths[j].Length)) {
                // 更新源点到vj的路径（paths[k]是源点到vk的最短路径)。
                paths[j].Length = paths[k].Length + graph[k][j];
                // 路径j的上一个顶点应该更新为k（即源点到vj是经过vk到达vj的）。
                paths[j].Predecessor = k;
            }
        }

        /**
         * 3.寻找图G中已知的最短路径。并以该路径的终点为新的立足点探索最短路径。
         * 新立足点Vk，其需满足以下条件：
         * 1.未曾作为立足点，即paths[k].IsVisited为false。
         * 2.路径最小，即paths[k].Length为Min(paths[0].Length, ..., paths[n-1].Length)
         */
        let min: number = infinity;    // 设当前最小值为无穷。
        for (let j = 0; j < numberOfVertexes; j++) {
            if (paths[j].IsVisited)    // 若曾作为立足点，则跳过并转向下一个。
                continue;
            if (paths[j].Length < min) // 发现更小的路径：
            {
                k = j;                 // 记录下顶点下标（编号）。
                min = paths[j].Length; // 记录下最小路径。
            }
        }                              // 在paths[k]处找到最小路径。
    }

    // 输出结果
    console.log(printResult(paths, initialVertex));
}

function dijkstraSimplified(graph: number[][], initialVertex: number, numberOfVertexes: number): void {
    /** 
     * 源点到以数组paths的下标为下标的顶点的最短路径
     * 的长度（或权重累加和）。
     * 比如：paths[2]，表示源点到顶点v2的最短路径。
     */
    // 0.初始化（转换为数组，而不用类。）
    let lengths: number[] = [];
    let predecessors: number[] = [];
    let isVisiteds: boolean[] = [];

    //Path[] paths = new Path[numberOfVertexes];

    /**
     * 每条路径设为初始值。
     */
    for (let i = 0; i < numberOfVertexes; i++) {
        lengths[i] = infinity;
        predecessors[i] = -1;
        isVisiteds[i] = false;
    }

    let k: number = initialVertex;               // 从源点开始寻找最短路径。
    lengths[k] = 0;                              // 源点->源点的路径为0。
    predecessors[k] = k;                         // 源点->源点的路径的前驱（上一个）顶点就是源点。如：(v1, v1)。

    /**
     * 图G有n个顶点。需要以图中各顶点作为最短路径的立足
     * 点探索最短路径。
     */
    // 逐个顶点探索最短路径。
    for (let i = 0; i < numberOfVertexes; i++) {
        // 1.以Vk为立足点探索它到其余顶点的最短路径。
        isVisiteds[k] = true;

        /**
        * 2.探索Vk的最短路径。从Vk到其余各与Vk相关联的顶点。
        */
        for (let j = 0; j < numberOfVertexes; j++) {
            /**
             * 若
             * 1.paths[j]对应的终点未曾作为立足点。（Vj未曾作为立足点。）
             * 2.存在边(Vk, Vj)。
             * 3.当前最短路径paths[k]的终点Vk到Vj的路径比已经探索到的源点到Vj的路径paths[j]还更短。
             * 则需要更新paths[j]，即发现路一条到vj的新路径且比已知长度更短。
             */
            if (isVisiteds[j] == false &&
                graph[k][j] != infinity &&
                (lengths[k] + graph[k][j] < lengths[j])) {
                // 更新源点到vj的路径（paths[k]是源点到vk的最短路径)。
                lengths[j] = lengths[k] + graph[k][j];
                // 路径j的上一个顶点应该更新为k（即源点到vj是经过vk到达vj的）。
                predecessors[j] = k;
            }
        }

        /**
         * 3.寻找图G中已知的最短路径。并以该路径的终点为新的立足点探索最短路径。
         * 新立足点Vk，其需满足以下条件：
         * 1.未曾作为立足点，即paths[k].IsVisited为false。
         * 2.路径最小，即paths[k].Length为Min(paths[0].Length, ..., paths[n-1].Length)
        */
        let min: number = infinity;       // 设当前最小值为无穷。
        for (let j = 0; j < numberOfVertexes; j++) {
            if (isVisiteds[j])            // 若曾作为立足点，则跳过并转向下一个。
                continue;
            if (lengths[j] < min)         // 发现更小的路径：
            {
                k = j;                   // 记录下顶点下标（编号）。
                min = lengths[j];        // 记录下最小路径。
            }
        }                                // 在paths[k]处找到最小路径。
    }

    // 输出结果
    for (let i = 0; i < numberOfVertexes; i++) {
        let result: string = "";
        let cursor: number = i;

        if (cursor == initialVertex) {
            result = `->${cursor}`;
        }

        while (cursor != initialVertex) {
            result = `->${cursor}${result}`;
            cursor = predecessors[cursor];
        }
        result = `${cursor}${result}: ${lengths[i]}`;
        console.log(result);
    }
}

function printResult(paths: Path[], initialVertex: number): string {

    let numberOfVertexes = paths.length;

    let result: string = "";

    for (let i = 0; i < numberOfVertexes; i++) {
        let line: string = "";
        let cursor = i;

        if (cursor === initialVertex) {
            line = `->${cursor}`;
        }

        while (cursor != initialVertex) {
            line = `->${cursor}${line}`;
            cursor = paths[cursor].Predecessor;
        }
        line = `${cursor}${line}: ${paths[i].Length}`;
        result = result.concat(line, "\n");
    }

    return result;
}

function Main() {
    let numberOfVertexes: number = 9;

    let graph: number[][] = [
        [0, 1, 5, infinity, infinity, infinity, infinity, infinity, infinity],
        [1, 0, 3, 7, 5, infinity, infinity, infinity, infinity],
        [5, 3, 0, infinity, 1, 7, infinity, infinity, infinity],
        [infinity, 7, infinity, 0, 2, infinity, 3, infinity, infinity],
        [infinity, 5, 1, 2, 0, 3, 6, 9, infinity],
        [infinity, infinity, 7, infinity, 3, 0, infinity, 5, infinity],
        [infinity, infinity, infinity, 3, 6, infinity, 0, 2, 7],
        [infinity, infinity, infinity, infinity, 9, 5, 2, 0, 4],
        [infinity, infinity, infinity, infinity, infinity, infinity, 7, 4, 0],
    ];

    dijkstra(graph, 5, numberOfVertexes);
    dijkstraSimplified(graph, 5, numberOfVertexes);
}

Main();

/**
运行结果：
0->0: 0
0->1: 1
0->1->2: 4
0->1->2->4->3: 7
0->1->2->4: 5
0->1->2->4->5: 8
0->1->2->4->3->6: 10
0->1->2->4->3->6->7: 12
0->1->2->4->3->6->7->8: 16
 */

参考资料：

《大话数据结构》 - 程杰著 - 清华大学出版社
《我的第一本算法书》 - 宫崎修一 & 石田保辉著 - 人民邮电出版社或《算法动画图解》iOS App

码农公寓

引入

演示

伪代码

分析

代码

C#代码

相关文章