狄克斯特拉（Dijkstra）优化算法

引进

从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，从端点V4开始下一轮找寻。

流程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，从端点V8开始下一轮找寻。

流程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.V7与V4、V5、V6、V7及V8相接。
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 = ∞;
        // 解析xml全部途径。
        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-一个
            {
                Console.Write($"{ToInfinity(array[i])}, ");
            }
            if (array.Length > 0)                       // 輸出二维数组的最终一个
            {
                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