编程知识 cdmana.com

Dijkstra algorithm

introduce

from A Point to B What is the shortest path of a point ? Two algorithms for finding the shortest path :Dijkstra Algorithm and Floyd Algorithm .

Net diagram : With weight chart .

The shortest path of non net graph : The path with the least number of edges between two vertices .( Non net graph can also be understood as the weight of each side is 1 Network diagram of .)

The shortest path of the net graph : The path with the least sum of weights on the edge between two vertices . The first vertex on the path is the source point , The last vertex is the end .

problem : The following figure V0 Point to the other vertices Vk What is the shortest path for ?

 Find the shortest path from the source point to each point

demonstration

Set up a picture G Each vertex in is V0 The path to that point . And expressed in the following form :

Path[x].Length:V0 To the end of the path V[x] Shortest path . Such as Path[2].Length by V0->V2 Shortest path .

Path[x].Predecessor:V0 The number of the last vertex to the end of the path ( Subscript ). Such as Path[2].Predecessor by 0, Express V0->V2 Shortest path , The vertices V2 The previous vertex of is V1, That is, through V1 Then arrive at V2.

Path[x].IsVisited: The vertices Vx Have you ever used it as a foothold to find the shortest path . among Vx yes V0 To the end of the path .

G[i][j]: Graph is represented by adjacency matrix G.G[i][j] For the top Vi To the top Vj A weight .

0. initialization :
Of all paths Predecessor Set to -1,Length Set to 0,IsVisited Set to false.
From the source Path[0].Predecessor = 0, because V0->V0 One vertex on the path is V0,V0->V0 The distance to 0, so Path[0].Length = 0.

step 0:

 step 0

1. With V0 For a foothold , therefore Path[0].IsVisited = true.
2.V0 And V0、V1 And V2 Connected to a .
Path[0].IsVisited by true, So skip this path .

Path[0].Length + G[0][1] = 0 + 1 < Path[2].Length = ∞ so Path[1].Length = 1,Path[1].Predecessor = 0;

Path[0].Length + G[0][2] = 0 + 5 < Path[2].Length = ∞ so Path[2].Length = 5,Path[2].Predecessor = 0;

3. Now look up the picture G All in 9 A path ( Every vertex forms a shortest path ) Which path has not been used as a foothold and the shortest path has the end point as a new foothold .
Path[0].IsVisited by true, So skip . And the rest are false.
Path[1].Length by 1,Path[2].Length by 5, rest Path.Length by ∞. So choose Path[1] The end V1 As a new foothold . Make V0 = 1, From the top V1 Start the next round of search .

step 1:

 step 1

1. With V1 For a foothold , therefore Path[1].IsVisited = true.
2.V1 And V0、V1、V2、V3 And V4 Connected to a .
Path[0].IsVisited by true,Path[1].IsVisited by true, So skip these paths .

Path[1].Length + G[1][2] = 1 + 3 < Path[2].Length = 5 so Path[2].Length = 4,Path[2].Predecessor = 1;

Path[1].Length + G[1][3] = 1 + 7 < Path[3].Length = ∞ so Path[3].Length = 8,Path[3].Predecessor = 1;

Path[1].Length + G[1][4] = 1 + 5 < Path[4].Length = ∞ so Path[4].Length = 6,Path[4].Predecessor = 1;

3. Now look up the picture G All in 9 A path ( Every vertex forms a shortest path ) Which path has not been used as a foothold and the shortest path has the end point as a new foothold .
Path[0、1].IsVisited by true, So skip . And the rest are false.
Path[2].Length by 4,Path[3].Length by 8,Path[4].Length by 6, rest Path.Length by ∞. So choose Path[2] The end V2 As a new foothold . Make V0 = 2, From the top V2 Start the next round of search .

step 2:

 step 2

1. With V2 For a foothold , therefore Path[2].IsVisited = true.
2.V2 And V0、V1、V2、V4、 And V5 Connected to a .
Path[0、1、2].IsVisited by true, So skip these paths .

Path[2].Length + G[2][4] = 4 + 1 < Path[4].Length = 6 so Path[4].Length = 5,Path[4].Predecessor = 2;

Path[2].Length + G[2][5] = 4 + 7 < Path[5].Length = ∞ so Path[5].Length = 11,Path[5].Predecessor = 2;

3. Now look up the picture G All in 9 A path ( Every vertex forms a shortest path ) Which path has not been used as a foothold and the shortest path has the end point as a new foothold .
Path[0、1、2].IsVisited by true, So skip . And the rest are false.
Path[3].Length by 8,Path[4].Length by 5,Path[5].Length by 11, rest Path.Length by ∞. So choose Path[4] The end V4 As a new foothold . Make V0 = 4, From the top V4 Start the next round of search .

step 3:

 step 3

1. With V4 For a foothold , therefore Path[4].IsVisited = true.
2.V4 And V1、V2、V3、V4、V5、V6 And V7 Connected to a .
Path[0、1、2、4].IsVisited by true, So skip these paths .

Path[4].Length + G[4][3] = 5 + 2 < Path[3].Length = 8 so Path[3].Length = 7,Path[3].Predecessor = 4;

Path[4].Length + G[4][5] = 5 + 3 < Path[5].Length = 11 so Path[5].Length = 8,Path[5].Predecessor = 4;

Path[4].Length + G[4][6] = 5 + 6 < Path[6].Length = ∞ so Path[6].Length = 11,Path[6].Predecessor = 4;

Path[4].Length + G[4][7] = 5 + 9 < Path[7].Length = ∞ so Path[7].Length = 14,Path[6].Predecessor = 4;

3. Now look up the picture G All in 9 A path ( Every vertex forms a shortest path ) Which path has not been used as a foothold and the shortest path has the end point as a new foothold .
Path[0、1、2、4].IsVisited by true, So skip . And the rest are false.
Path[3].Length by 7,Path[5].Length by 8,Path[6].Length by 11,Path[7].Length by 14, rest Path.Length by ∞. So choose Path[3] The end V3 As a new foothold . Make V0=3, From the top V3 Start the next round of search .

step 4:

 step 4

1. With V3 For a foothold , therefore Path[3].IsVisited = true.
2.V3 And V1、V4 And V6 Connected to a .
Path[0、1、2、3、4].IsVisited by true, So skip these paths .

Path[3].Length + G[3][6] = 7 + 3 < Path[6].Length = 11 so Path[6].Length = 10,Path[6].Predecessor = 3;

3. Now look up the picture G All in 9 A path ( Every vertex forms a shortest path ) Which path has not been used as a foothold and the shortest path has the end point as a new foothold .
Path[0、1、2、3、4].IsVisited by true, So skip . And the rest are false.
Path[5].Length by 8,Path[6].Length by 10,Path[7].Length by 14, rest Path.Length by ∞. So choose Path[5] The end V5 As a new foothold . Make V0 = 5, From the top V5 Start the next round of search .

step 5:

 step 5

1. With V5 For a foothold , therefore Path[5].IsVisited = true.
2.V5 And V2、V4、V5 And V7 Connected to a .
Path[0、1、2、3、4、5].IsVisited by true, So skip these paths .

Path[5].Length + G[5][7] = 8 + 5 < Path[7].Length = 14 so Path[7].Length = 13,Path[7].Predecessor = 5;

3. Now look up the picture G All in 9 A path ( Every vertex forms a shortest path ) Which path has not been used as a foothold and the shortest path has the end point as a new foothold .
Path[0、1、2、3、4、5].IsVisited by true, So skip . And the rest are false.
Path[6].Length by 10,Path[7].Length by 13, rest Path.Length by ∞. So choose Path[6] The end V6 As a new foothold . Make V0 = 6, From the top V6 Start the next round of search .

step 6:

 step 6

1. With V6 For a foothold , therefore Path[6].IsVisited = true.
2.V6 And V3、V4、V7 And V8 Connected to a .
Path[0、1、2、3、4、5、6].IsVisited by true, So skip these paths .

Path[6].Length + G[6][7] = 10 + 2 < Path[7].Length = 13 so Path[7].Length = 12,Path[7].Predecessor = 6;

Path[6].Length + G[6][8] = 10 + 7 < Path[8].Length = ∞ so Path[8].Length = 17,Path[8].Predecessor = 6;

3. Now look up the picture G All in 9 A path ( Every vertex forms a shortest path ) Which path has not been used as a foothold and the shortest path has the end point as a new foothold .
Path[0、1、2、3、4、5、6].IsVisited by true, So skip . And the rest are false.
Path[7].Length by 12,Path[8].Length by 17, There is no other Path 了 . So choose Path[7] The end V7 As a new foothold . Make V0 = 7, From the top V7 Start the next round of search .

step 7:

 step 7

1. With V7 For a foothold , therefore Path[7].IsVisited = true.
2.V7 And V4、V5、V6、V7 And V8 Connected to a .
Path[0、1、2、3、4、5、6、7].IsVisited by true, So skip these paths .

Path[7].Length + G[7][8] = 12 + 4<Path[8].Length = 17 so Path[8].Length = 16,Path[8].Predecessor = 7;

3. Now look up the picture G All in 9 A path ( Every vertex forms a shortest path ) Which path has not been used as a foothold and the shortest path has the end point as a new foothold .
Path[0、1、2、3、4、5、6、7].IsVisited by true, So skip . And the rest are false.
Path[8].Length by 16, Nothing else Path. So choose Path[8] The end V8 As a new foothold . Make V0 = 8, From the top V8 Start the next round of search .

step 8:

 step 8

1. With V8 For a foothold , therefore Path[8].IsVisited = true.
2.V8 And V6、V7 And V8 Connected to a .
Path[0、1、2、3、4、5、6、7、8].IsVisited by true, So skip these paths .

There's no path left to explore .

3. Now look up the picture G All in 9 A path ( Every vertex forms a shortest path ) Which path has not been used as a foothold and the shortest path has the end point as a new foothold .
Path[0、1、2、3、4、5、6、7、8].IsVisited by true, So skip . There's no path left to explore . There's no need to start the next round of searching .

Finish exploring ,Path An array is V0 The shortest path to each vertex . Output Path The array can be .
step 0~8 All operations in are repeated , Summarize and form code .

Pseudo code

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

    //  Set each path to its initial value .
    for (int i = 0; i < n; i++)
    {
        paths[i].Length = ∞;
        paths[i].Predecessor = -1;
        paths[i].IsVisited = false;
    }

    //  With v Find the shortest path for the source .
    int k = v;
    // v0->v0 The path length of is 0.
    paths[k].Length = 0;
    // v0->v0 The last vertex of the path is v0.
    paths[k].Predecessor = 0;

    //  Explore the shortest path one by one .
    for (int i = 0; i < n; i++)
    {
        // 1. With vk Find the shortest path to the rest of the vertices for the foothold .
        paths[k].IsVisited = true;
        // 2. Explore vk Shortest path 
        for (int j = 0; j < n; j++)
        {
            // vj Not as a foothold  &&
            //  There are edges (vk, vj) &&
            // vk To vj The length of the current path is longer than that of the source point that has been explored vj The path is shorter .
            if (paths[j].IsVisited = false &&
                g[k][j] != ∞ &&
                paths[k].Length + g[k][j] < paths[j].Length)
            {
                //  Update source point to vj The path of (paths[k] It's from the source to vk Shortest path ).
                paths[j].Length = paths[k].Length + g[k][j];
                //  route j The previous vertex of should be updated to k( From the source point to vj Is a vk arrive vj Of ).
                paths[j].Predecessor = k;
            }
        }

        // 3. Look for pictures G The shortest path known in . And take the end of the path as a new foothold to explore the shortest path .
        //  Let the current minimum be infinite .
        int min = ∞;
        //  Traverse all paths .
        for (int j = 0; j < n; j++)
        {
            //  The end of the path used to be the path of the foothold , It is the shortest path .
            //  The end of the path does not need to be used as a foothold to explore the shortest path .
            //  so , Just skip .
            if (paths[j].IsVisited == true)
            {
                continue;
            }

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

        //  here k It is the subscript of the new shortest path .
    }

    //  Output paths, Each path is the shortest path from the source to the end of the path .
}

analysis

Dijkstra The algorithm solves the shortest path problem from a source point to other points . From the loop nesting, we can see that the time complexity of the algorithm is O(n2).( Excerpt from 《 Big talk data structure 》.)

The difference between minimum spanning tree and minimum path

Minimum spanning tree : Map G It takes the shortest distance to connect all the vertices in ( The sum of all paths is the smallest ). Make sure that the sum of all paths in the graph is the shortest . But is one point closest to another , There is no guarantee .

Minimum path : From the picture G Set out at the top of a certain point , It takes the shortest distance to get to the other vertices . Ensure the shortest distance from one point to the rest , But is it the shortest way to connect all the points , Not necessarily .

for example : The minimum spanning tree and minimum path of the following graph .

 The difference between minimum spanning tree and minimum path

Code

Graph is represented by adjacency matrix G. as follows :

 chart G Adjacency matrix representation of

C# Code

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>
        ///  The shortest path from the source point to each vertex in the graph .
        /// </summary>
        /// <param name="graph"> chart G.</param>
        /// <param name="initialVertex"> Source point ( chart G The subscript of the vertex in the ), Any vertex in a graph can be a source point .</param>
        /// <param name="numberOfVertexes"> chart G The number of vertices in .</param>
        static void Dijkstra(int[][] graph, int initialVertex, int numberOfVertexes)
        {
            /** 
             *  Source point to array paths The subscript of is the shortest path of the subscript vertex 
             *  The length of ( Or the sum of weights ).
             *  such as :paths[2], Represents the source point to the vertex v2 Shortest path .
             */
            // 0. initialization 
            Path[] paths = new Path[numberOfVertexes];

            /**
             *  Each path is set to the initial value .
             */
            for (int i = 0; i < numberOfVertexes; i++)
            {
                paths[i] = new Path()
                {
                    Length = Constants.Infinity,
                    Predecessor = -1,
                    IsVisited = false
                };
            }

            int k = initialVertex;               //  Find the shortest path from the source .
            paths[k].Length = 0;                 //  Source point -> The path of the source point is 0.
            paths[k].Predecessor = k;            //  Source point -> The precursor of the path of the source point ( the previous ) The vertex is the source . Such as :(v1, v1).

            /**
             *  chart G Yes n vertices . We need to take each vertex in the graph as the foothold of the shortest path 
             *  Point to explore the shortest path .
             */
            //  Explore the shortest path one by one .
            for (int i = 0; i < numberOfVertexes; i++)
            {
                paths[k].IsVisited = true;       // 1. With Vk Explore its shortest path to the rest of the vertices for a foothold .

                /**
                * 2. Explore Vk Shortest path . from Vk The rest are related to Vk Associated vertices .
                */
                for (int j = 0; j < numberOfVertexes; j++)
                {
                    /**
                     *  if 
                     * 1.paths[j] The corresponding end has never been a foothold .(Vj Not as a foothold .)
                     * 2. There are edges (Vk, Vj).
                     * 3. The current shortest path paths[k] The end Vk To Vj The path ratio has been explored to the source point Vj The path of paths[j] It's shorter .
                     *  You need to update paths[j], That is to find a way to vj And shorter than the known length .
                     */
                    if (paths[j].IsVisited == false &&
                        graph[k][j] != Constants.Infinity &&
                        (paths[k].Length + graph[k][j] < paths[j].Length))
                    {
                        //  Update source point to vj The path of (paths[k] It's from the source to vk Shortest path ).
                        paths[j].Length = paths[k].Length + graph[k][j];
                        //  route j The previous vertex of should be updated to k( From the source point to vj Is a vk arrive vj Of ).
                        paths[j].Predecessor = k;
                    }
                }

                /**
                 * 3. Look for pictures G The shortest path known in . And take the end of the path as a new foothold to explore the shortest path .
                 *  A new foothold Vk, It needs to meet the following conditions :
                 * 1. Not as a foothold , namely paths[k].IsVisited by false.
                 * 2. The path is the smallest , namely paths[k].Length by Min(paths[0].Length, ..., paths[n-1].Length)
                */
                int min = Constants.Infinity;    //  Let the current minimum be infinite .
                for (int j = 0; j < numberOfVertexes; j++)
                {
                    if (paths[j].IsVisited)      //  If ever as a foothold , Then skip and go to the next .
                        continue;
                    if (paths[j].Length < min)   //  Find smaller paths :
                    {
                        k = j;                   //  Record the vertex subscripts ( Number ).
                        min = paths[j].Length;   //  Record the minimum path .
                    }
                }                                //  stay paths[k] Find the minimum path at .
            }

            //  Output results 
            PrintResult(paths, initialVertex);
        }

        static void DijkstraSimplified(int[][] graph, int initialVertex, int numberOfVertexes)
        {
            /** 
             *  Source point to array paths The subscript of is the shortest path of the subscript vertex 
             *  The length of ( Or the sum of weights ).
             *  such as :paths[2], Represents the source point to the vertex v2 Shortest path .
             */
            // 0. initialization ( Convert to array , Instead of classes .)
            //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];

            /**
             *  Each path is set to the initial value .
             */
            for (int i = 0; i < numberOfVertexes; i++)
            {
                lengths[i] = Constants.Infinity;
                predecessors[i] = -1;
                isVisiteds[i] = false;
                
            }

            int k = initialVertex;               //  Find the shortest path from the source .
            lengths[k] = 0;                      //  Source point -> The path of the source point is 0.
            predecessors[k] = k;                 //  Source point -> The precursor of the path of the source point ( the previous ) The vertex is the source . Such as :(v1, v1).

            /**
             *  chart G Yes n vertices . We need to take each vertex in the graph as the foothold of the shortest path 
             *  Point to explore the shortest path .
             */
            //  Explore the shortest path one by one .
            for (int i = 0; i < numberOfVertexes; i++)
            {
                // 1. With Vk Explore its shortest path to the rest of the vertices for a foothold .
                isVisiteds[k] = true;

                /**
                * 2. Explore Vk Shortest path . from Vk The rest are related to Vk Associated vertices .
                */
                for (int j = 0; j < numberOfVertexes; j++)
                {
                    /**
                     *  if 
                     * 1.paths[j] The corresponding end has never been a foothold .(Vj Not as a foothold .)
                     * 2. There are edges (Vk, Vj).
                     * 3. The current shortest path paths[k] The end Vk To Vj The path ratio has been explored to the source point Vj The path of paths[j] It's shorter .
                     *  You need to update paths[j], That is to find a way to vj And shorter than the known length .
                     */
                    if (isVisiteds[j] == false &&
                        graph[k][j] != Constants.Infinity &&
                        (lengths[k] + graph[k][j] < lengths[j]))
                    {
                        //  Update source point to vj The path of (paths[k] It's from the source to vk Shortest path ).
                        lengths[j] = lengths[k] + graph[k][j];
                        //  route j The previous vertex of should be updated to k( From the source point to vj Is a vk arrive vj Of ).
                        predecessors[j] = k;
                    }
                }

                /**
                 * 3. Look for pictures G The shortest path known in . And take the end of the path as a new foothold to explore the shortest path .
                 *  A new foothold Vk, It needs to meet the following conditions :
                 * 1. Not as a foothold , namely paths[k].IsVisited by false.
                 * 2. The path is the smallest , namely paths[k].Length by Min(paths[0].Length, ..., paths[n-1].Length)
                */
                int min = Constants.Infinity;    //  Let the current minimum be infinite .
                for (int j = 0; j < numberOfVertexes; j++)
                {
                    if (isVisiteds[j])           //  If ever as a foothold , Then skip and go to the next .
                        continue;
                    if (lengths[j] < min)        //  Find smaller paths :
                    {
                        k = j;                   //  Record the vertex subscripts ( Number ).
                        min = lengths[j];        //  Record the minimum path .
                    }
                }                                //  stay paths[k] Find the minimum path at .
            }

            //  Output results 
            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++)  //  The front of the output array n-1 individual 
            {
                Console.Write($"{ToInfinity(array[i])}, ");
            }
            if (array.Length > 0)                       //  At the end of the output array 1 individual 
            {
                int n = array.Length - 1;
                Console.Write($"{ToInfinity(array[n])}");
            }
            Console.WriteLine(" ]");
        }

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

    /**
     *  Path class . Source points to the rest of the vertices in the graph vk Shortest path .
     */
    public class Path
    {
        //  Source to vertex vk The path length of .( The sum of the weights of the sides of the path . This value is ultimately the shortest path length .)
        public int Length { get; set; } = Constants.Infinity;
        //  The last vertex the path ends at ( The subscript ).
        public int Predecessor { get; set; } = -1;
        //  Has the end of the path ever been a foothold .
        public bool IsVisited { get; set; } = false;
    }

    /**
     *  Classes that represent constants .
     */
    public static class Constants
    {
        public static int Infinity { get => int.MaxValue; }
    }
}

/**
 Running results :
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 Code

const infinity: number = Number.MAX_VALUE;

/**
 *  Path class . Source points to the rest of the vertices in the graph vk Shortest path .
 */
class Path {
    //  Source to vertex vk The path length of .( The sum of the weights of the sides of the path . This value is ultimately the shortest path length .)
    Length: number = 0;
    //  The last vertex the path ends at ( The subscript ).
    Predecessor: number = -1;
    //  Has the end of the path ever been a foothold .
    IsVisited: boolean = false;
}

/**
 *  The shortest path from the source point to each vertex in the graph .
 * @param graph  chart G.
 * @param initialVertex  Source point ( chart G The subscript of the vertex in the ), Any vertex in a graph can be a source point .
 * @param numberOfVertexes  chart G The number of vertices in .
 * @author kokiafan 
 */
function dijkstra(graph: number[][], initialVertex: number, numberOfVertexes: number): void {
    /** 
     *  Source point to array paths The subscript of is the shortest path of the subscript vertex 
     *  The length of ( Or the sum of weights ).
     *  such as :paths[2], Represents the source point to the vertex v2 Shortest path .
     */
    // 0. initialization 
    let paths: Path[] = [];

    /**
     *  Each path is set to the initial value .
     */
    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;     //  Find the shortest path from the source .
    paths[k].Length = 0;               //  Source point -> The path of the source point is 0.
    paths[k].Predecessor = k;          //  Source point -> The precursor of the path of the source point ( the previous ) The vertex is the source . Such as :(v1, v1).
    /**
     *  chart G Yes n vertices . We need to take each vertex in the graph as the foothold of the shortest path 
     *  Point to explore the shortest path .
     */
    //  Explore the shortest path one by one .
    for (let i = 0; i < numberOfVertexes; i++) {
        // 1. With Vk Explore its shortest path to the rest of the vertices for a foothold .
        paths[k].IsVisited = true;

        /**
        * 2. Explore Vk Shortest path . from Vk The rest are related to Vk Associated vertices .
        */
        for (let j = 0; j < numberOfVertexes; j++) {
            /**
             *  if 
             * 1.paths[j] The corresponding end has never been a foothold .(Vj Not as a foothold .)
             * 2. There are edges (Vk, Vj).
             * 3. The current shortest path paths[k] The end Vk To Vj The path ratio has been explored to the source point Vj The path of paths[j] It's shorter .
             *  You need to update paths[j], That is to find a way to vj And shorter than the known length .
             */
            if (paths[j].IsVisited == false &&
                graph[k][j] != infinity &&
                (paths[k].Length + graph[k][j] < paths[j].Length)) {
                //  Update source point to vj The path of (paths[k] It's from the source to vk Shortest path ).
                paths[j].Length = paths[k].Length + graph[k][j];
                //  route j The previous vertex of should be updated to k( From the source point to vj Is a vk arrive vj Of ).
                paths[j].Predecessor = k;
            }
        }

        /**
         * 3. Look for pictures G The shortest path known in . And take the end of the path as a new foothold to explore the shortest path .
         *  A new foothold Vk, It needs to meet the following conditions :
         * 1. Not as a foothold , namely paths[k].IsVisited by false.
         * 2. The path is the smallest , namely paths[k].Length by Min(paths[0].Length, ..., paths[n-1].Length)
         */
        let min: number = infinity;    //  Let the current minimum be infinite .
        for (let j = 0; j < numberOfVertexes; j++) {
            if (paths[j].IsVisited)    //  If ever as a foothold , Then skip and go to the next .
                continue;
            if (paths[j].Length < min) //  Find smaller paths :
            {
                k = j;                 //  Record the vertex subscripts ( Number ).
                min = paths[j].Length; //  Record the minimum path .
            }
        }                              //  stay paths[k] Find the minimum path at .
    }

    //  Output results 
    console.log(printResult(paths, initialVertex));
}

function dijkstraSimplified(graph: number[][], initialVertex: number, numberOfVertexes: number): void {
    /** 
     *  Source point to array paths The subscript of is the shortest path of the subscript vertex 
     *  The length of ( Or the sum of weights ).
     *  such as :paths[2], Represents the source point to the vertex v2 Shortest path .
     */
    // 0. initialization ( Convert to array , Instead of classes .)
    let lengths: number[] = [];
    let predecessors: number[] = [];
    let isVisiteds: boolean[] = [];

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

    /**
     *  Each path is set to the initial value .
     */
    for (let i = 0; i < numberOfVertexes; i++) {
        lengths[i] = infinity;
        predecessors[i] = -1;
        isVisiteds[i] = false;
    }

    let k: number = initialVertex;               //  Find the shortest path from the source .
    lengths[k] = 0;                              //  Source point -> The path of the source point is 0.
    predecessors[k] = k;                         //  Source point -> The precursor of the path of the source point ( the previous ) The vertex is the source . Such as :(v1, v1).

    /**
     *  chart G Yes n vertices . We need to take each vertex in the graph as the foothold of the shortest path 
     *  Point to explore the shortest path .
     */
    //  Explore the shortest path one by one .
    for (let i = 0; i < numberOfVertexes; i++) {
        // 1. With Vk Explore its shortest path to the rest of the vertices for a foothold .
        isVisiteds[k] = true;

        /**
        * 2. Explore Vk Shortest path . from Vk The rest are related to Vk Associated vertices .
        */
        for (let j = 0; j < numberOfVertexes; j++) {
            /**
             *  if 
             * 1.paths[j] The corresponding end has never been a foothold .(Vj Not as a foothold .)
             * 2. There are edges (Vk, Vj).
             * 3. The current shortest path paths[k] The end Vk To Vj The path ratio has been explored to the source point Vj The path of paths[j] It's shorter .
             *  You need to update paths[j], That is to find a way to vj And shorter than the known length .
             */
            if (isVisiteds[j] == false &&
                graph[k][j] != infinity &&
                (lengths[k] + graph[k][j] < lengths[j])) {
                //  Update source point to vj The path of (paths[k] It's from the source to vk Shortest path ).
                lengths[j] = lengths[k] + graph[k][j];
                //  route j The previous vertex of should be updated to k( From the source point to vj Is a vk arrive vj Of ).
                predecessors[j] = k;
            }
        }

        /**
         * 3. Look for pictures G The shortest path known in . And take the end of the path as a new foothold to explore the shortest path .
         *  A new foothold Vk, It needs to meet the following conditions :
         * 1. Not as a foothold , namely paths[k].IsVisited by false.
         * 2. The path is the smallest , namely paths[k].Length by Min(paths[0].Length, ..., paths[n-1].Length)
        */
        let min: number = infinity;       //  Let the current minimum be infinite .
        for (let j = 0; j < numberOfVertexes; j++) {
            if (isVisiteds[j])            //  If ever as a foothold , Then skip and go to the next .
                continue;
            if (lengths[j] < min)         //  Find smaller paths :
            {
                k = j;                   //  Record the vertex subscripts ( Number ).
                min = lengths[j];        //  Record the minimum path .
            }
        }                                //  stay paths[k] Find the minimum path at .
    }

    //  Output results 
    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();

/**
 Running results :
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
 */

Reference material :

《 Big talk data structure 》 - gemee Writing - tsinghua university press
《 My first algorithm book 》 - Miyazaki Shoichi & Ishida Baohui Writing - People's post and Telecommunications Press or 《 Algorithm animation illustration 》iOS App

版权声明
本文为[kokiafan]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/05/20210522122819974g.html

Scroll to Top