当前位置： 正文

探索最短路

2021-05-23 技术推文 5.47k 推广

摘要

介绍最短路径算法的两种优化方法：Dijkstra和Floyd。它们适用于带权图，即边有权重值的图。这些算法可以帮助我们找到从一个点到另一个点的最短路径。但是，有时候我们需要在非网图中找到最短路径，这意味着我们只需要考虑经过的边数。在网图中，我们需要考虑边的权重值。这些算法可以帮助我们解决这些难题。

正文

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

引进

从A点到B点的最短路径算法是啥？求最短路径算法的二种优化算法：Dijkstra优化算法和Floyd优化算法。

网图：带权图。

非网图最短路径算法：两端点间历经的边数至少的途径。（非网图也可被了解为各边权重值为1的网图。）

网图最短路径算法：两端点间历经的旁边权重值之和至少的途径。途径上第一个端点是源点，最终的端点是终点站。

难题：下面的图中V0 点至其他每个端点Vk的最短路径算法是啥？

求该图源点到各点的最短路径

演试

设图G中的每一个端点为V0到该点的途径。并且用下列方式来表明：

Path[x].Length：V0到该途径所处终点站的V[x]的最短路径算法。如Path[2].Length为V0->V2的最短路径算法。

Path[x].Predecessor：V0到该途径所处终点站的上一个端点的序号（字符）。如Path[2].Predecessor为0，表明V0->V2的最短路径算法，端点V2的前一个端点为V1，即历经V1随后抵达V2。

Path[x].IsVisited：端点Vx是不是曾做为出发点来搜索下面的最短路径算法。在其中Vx是V0到该途径所在的终点站。

G[i][j]：用邻接矩阵表明图G。G[i][j]为端点Vi到端点Vj的权重值。

0.复位：
全部途径的Predecessor设成-1，Length设成0，IsVisited设成false。
从源点逐渐Path[0].Predecessor = 0，由于V0->V0途径上的一个端点为V0，V0->V0的间距为0，故Path[0].Length = 0。

流程0：

步骤0

1.以V0为出发点，因此Path[0].IsVisited = true。
2.V0与V0、V1及V2相接。
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做为新的出发点。令V0 = 1，从端点V1逐渐下一轮找寻。

流程1：

步骤1

1.以V1为出发点，因此Path[1].IsVisited = true。
2.V1与V0、V1、V2、V3及V4相接。
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做为新的出发点。令V0 = 2，从端点V4开始下一轮找寻。

流程2：

步骤2

1.以V2为出发点，因此Path[2].IsVisited = true。
2.V2与V0、V1、V2、V4、及V5相接。
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]的终点站V4做为新的出发点。令V0 = 4，从端点V8开始下一轮找寻。

流程3：

步骤3

1.以V4为出发点，因此Path[4].IsVisited = true。
2.V4与V1、V2、V3、V4、V5、V6及V7相接。
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]的终点站V3做为新的出发点。令V0=3，从端点V3逐渐下一轮找寻。

流程4：

步骤4

1.以V3为出发点，因此Path[3].IsVisited = true。
2.V3与V1、V4及V6相接。
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做为新的出发点。令V0 = 5，从端点V5逐渐下一轮找寻。

流程5：

步骤5

1.以V5为出发点，因此Path[5].IsVisited = true。
2.V5与V2、V4、V5及V7相接。
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做为新的出发点。令V0 = 6，从端点V6逐渐下一轮找寻。

流程6：

步骤6

1.以V6为出发点，因此Path[6].IsVisited = true。
2.V6与V3、V4、V7及V8相接。
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做为新的出发点。令V0 = 7，从端点V7逐渐下一轮找寻。

流程7：

步骤7

1.以V7为出发点，因此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做为新的出发点。令V0 = 8，从端点V8逐渐下一轮找寻。

流程8：

步骤8

1.以V8为出发点，因此Path[8].IsVisited = true。
2.V8与V6、V7及V8相接。
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二维数组就是V0到各端点的最短路径算法。輸出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。以下：

图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

关注不迷路

扫码下方二维码，关注宇凡盒子公众号，免费获取最新技术内幕！

温馨提示：如果您访问和下载本站资源，表示您已同意只将下载文件用于研究、学习而非其他用途。
文章版权声明 1、本网站名称：宇凡盒子
2、本站文章未经许可，禁止转载！
3、如果文章内容介绍中无特别注明，本网站压缩包解压需要密码统一是：yufanbox.com
4、本站仅供资源信息交流学习，不保证资源的可用及完整性，不提供安装使用及技术服务。点此了解
5、如果您发现本站分享的资源侵犯了您的权益，请及时通知我们，我们会在接到通知后及时处理！提交入口
赏 0

大家在看

物联网流量卡在IOS手机上无法分享个人热点问题解决办法
技术推文
WIFI热点个人热点开启WIFI热点

苹果手机无法开启个人热点是因为其APN接入点默认为空。要解决这个问题，需要在设置中添加物联卡的APN。下面是设置步骤：确认物联卡已激活并开通数据流量，进入设置-移动蜂窝网络-蜂窝移动数据网络-移动数据网络，点击右上角+号添加APN，按照提供的APN信息填写并保存即可。这样就能顺利地开启个人热点了。
2024-04-27 641
微信使用指南：保护账号安全，学会玩转微信！
技术推文
微信养号

众所周知，微信的重要性不言而喻，如果不幸被封，对我们的工作将带来巨大的影响。因此，今天我给大家带来一套相关的教程，从选择手机和手机卡开始，到注册微信号，再到养号和处理被封的方式，都会详细介绍。这套教程非常全面且细致，正如磨刀不误砍柴工一样，学起来吧！
2023-12-03 697
最新申请Openai，GPT4.0 API Key完整详细图文教程
技术推文
ChatGPTChatGPT官网CVV安全码

最新动态： OpenAI在官网宣布，GPT-4 API全面开放使用。 GPT宣布只要有过付费...
2023-11-15 1.12k
测试5个配音软件，我选了这个免费软件。
技术推文
微软工具tts腾讯智影配音神器

这几天我研究了5款配音软件，最终找到了让自己满意的免费软件。现在我来分享一下，供网友参考，一起交流链接。
2023-11-14 677
小红书未实名账号手机号释放方法
技术推文
小红书小红书换绑手机号释放

以前在平台上搜索不到自己账号的内容，很可能是因为系统限制了流量。现在你需要考虑的是，你的账号可能会被封禁。
2023-11-02 923
京东 Plus 会员限时活动，99 元即可回本，双 11 送券秒杀。
技术推文
京东PLUS活动线报

京东活动已于24号凌晨开始，现在只需99元即可享受Plus会员特权，还可获得50-40洗衣券和50元超市卡。此外，双11即将到来，屯个会员绝对划算！
2023-10-25 613

评论0

请先

站点公告

🚀 【宇凡盒子】全网资源库转储中心

👉 注册即送VIP权限👈

👻 全站资源免费下载✅，欢迎注册！

记得 【收藏】+【关注】 谢谢！~~~

立即注册
没有账号？注册  忘记密码？

社交账号快速登录