Figure - shortest path algorithm

Article directory

Shortest path algorithm

Single source shortest path algorithm

Single source shortest path:

Given the directed graph (or undirected graph) G=(V,E)G=(V,E)G=(V,E) and the source point V0 ∈ VV 0 \ in vv0 ∈ V, the shortest path (the sum of weights on the path to the minimum) from v0v ∈ 0v0 to the other vertices in GGG is obtained.

  1. A single source shortest path algorithm for weighted graphs

    1. Example: find the shortest path from v6v ﹣ 6v6 to the source vertex v1v ﹣ 1v1

      Note: the weights of the edges in the weighted graph must all be non negative, otherwise, a negative value circle will appear
      Example: find the shortest path from v5v to V4v

      If you walk along the loop {V5 → v4 → v2 → V5} \ {V {5 \ rightarrow V} {4 \ rightarrow V} 2 \ rightarrow V} {V5 → v4 → v2 → V5} many times, the path length from v5v {5v5 to V4v} will become infinitesimal without the shortest path.
      So in the following algorithms, only when the weight of the edge is greater than or equal to 0 is considered.

    2. Algorithm: Dijkstra algorithm

      • Let S = {source vertex v0 + vertex v with shortest path determined} S = \ {source vertex v_ + vertex v with shortest path determined \} S = {source vertex v0 + vertex v with shortest path determined}
      • For any uncollected vertex v v v, the definition of "Distence[v]Distence[v]Distence[v] is the shortest path length from the source point v0v_0v0 to vvv, but the path only passes through the vertices in the set SSS. And the minimum length of path {v0 → (V I ∈ S) → V} \ {V {0 \ rightarrow (V ∈ I \ in S) \ rightarrow V \} {v0 → (vi ∈ S) → V}, which is not the shortest path length
      • Select one of the uncollected vertices with the lowest value of distence [] distence [] into the set SSS
      • When the included vertex vvv enters the set SSS, it may affect the distence [] distence [] value of the adjacent vertices of the vertex vvv not included in the set SSS. Therefore, the value of distence [] distence [] may be updated every time the included vertex enters the set SSS
    3. PN code description

      void Dijkstra(Source SV)
      {
          while(1)
          {
              V = Not included in vertex Distence[]Least value person;
              if(In this way V Non-existent)
              {
                  break;
              }
              collected[V]=ture;//Include vertex V
              for(V Each adjacent node of W)
              {
                  if(collected[W]==false)
                  {
                      if(Distence[V] + edge<V,W>Weights < Distence[W])
                      {
                           Distence[W] = Distence[V] + edge<V,W>Weights;
                           Path[W] = V;//Array recording the shortest path
                      }
                  }
              }
          }
      }
      
    4. code implementation
      The figure is as follows:

      //Node representation of Graphs
        typedef struct GNode {
            int NV;//Vertex number
            int NE;//Edge number
            WeightType G[MaxVertexNum][MaxVertexNum];//Two dimensional array of type WeightType and size MaxVertexNum X MaxVertexNum forms adjacency matrix to save edge information
            //DataType Data[MaxVertexNum]; / / a one-dimensional array of DataType and MaxVertexNum size is used to store vertex information. Select as appropriate
        }GNode, *MGraph;
      

      There are two main ways to realize the "extract the minimum value of distence [] distence [] from pseudo code":

      1. utilize MinHeap

        //A single source shortest path algorithm for weighted graphs (with minimal heap)
        void DijkstraByMinHeap(MGraph G, Vertex SourceV)
        {
            MinHeap H = NULL;
            MinHeapElementType *Distence = NULL,Temp;
            int *Path = NULL;
            int V = 0, AdjV = 0;
            int i = 0;
        
            /************ Distence[]It is used to store the distance from each vertex to the source vertex, and Path [] is used to store the Path************/
            Distence = (MinHeapElementType *)malloc(sizeof(MinHeapElementType)*(G->NV));
            Path = (int *)malloc(sizeof(int)*(G->NV));
        
            /*************************** Initialize distance array********************************/
            for (i = 0; i < G->NV; i++)
            {
                Distence[i].Distance = INT_MAX;//The distance from all vertices (except the source vertex) to the source vertex is initialized to be positive infinity (replaced with int UU max)
                Distence[i].Vertex = -i - 1;//When Distence[].Vertex is negative, vertex i (i = - Vertex - 1) has not found the shortest path to the source vertex
                Path[i] = -1;
            }
            Distence[SourceV].Distance = 0;//The distance from the source vertex to the source vertex is initialized to 0
        
            /************************ Building a minimum heap with the Distence array***************************/
            H = BuildMinHeap(Distence, G->NV);
        
            /********************** Find the shortest path from all vertices to source vertices***********************/
            while (1)
            {
                //The minimum heap is used to store vertices where the shortest path is not found, so when the minimum heap is empty, the loop exits
                if (IsMinHeapEmpty(H))
                {
                    break;
                }
        
                //Temp stores the shortest path vertex data (path length and which vertex is the shortest path to the source vertex) among all vertices that have not found the shortest path
                Temp = DeleteMinHeap(H);
                V = -Temp.Vertex - 1;
                Distence[V].Distance = Temp.Distance;//The shortest distance from vertex V to source vertex was found
                Distence[V].Vertex = V;//Indicates that vertex V has found the shortest distance
        
                //All the neighboring vertices of traversing vertex V have not found the shortest path yet
                for (AdjV = 0; AdjV < G->NV; AdjV++)
                {
                    if ((G->G[V][AdjV] != 0) && (Distence[AdjV].Vertex < 0))
                    {
                        //Because the shortest distance from the vertex v to the source vertex is found, the distance from the critical vertex of V to the source vertex may change, check.
                        if (Distence[AdjV].Distance > Distence[V].Distance + G->G[V][AdjV])
                        {
                            Distence[AdjV].Distance = Distence[V].Distance + G->G[V][AdjV];
                            Path[AdjV] = V;
        
                            //Determine the location of node AdjV in the minimum heap storage array and change its distance from the source vertex SourceV
                            for (i = 1; i <= H->Size; i++)
                            {
                                if (H->Element[i].Vertex == (-AdjV - 1))
                                {
                                    H->Element[i].Distance = Distence[AdjV].Distance;
                                    break;
                                }
                            }
        
                            //Since the previous step makes H - > element [i]. Release smaller, adjust the location of the elements in the minimum heap in a similar way to the insertion of the minimum heap
                            Temp = H->Element[i];
                            for ( ; H->Element[i / 2].Distance > Temp.Distance; i = i / 2)
                            {
                                H->Element[i] = H->Element[i / 2];
                            }
                            H->Element[i] = Temp;
                        }
                    }
                }
            }
        
            //Print shortest path length table
            printf("Distence[]: \n");
            for (i = 0; i < G->NV; i++)
            {
                printf("%3d", Distence[i].Distance);
            }
            printf("\n");
            for (i = 0; i < G->NV; i++)
            {
                printf("%3d", Distence[i].Vertex);
            }
        
            //Print shortest path table
            printf("\nPath[]: \n");
            for (i = 0; i < G->NV; i++)
            {
                printf("%3d", Path[i]);
            }
        
        
            //Free space for application
            DestroyMinHeap(H);
            free(Distence);
            free(Path);
        }
        
      2. Direct array sorting

        //A single source shortest path algorithm for weighted graphs (direct sorting)
        void DijkstraBySort(MGraph G, Vertex SourceV)
        {
            List L = NULL;
            ListElementType *Distence = NULL, Temp;
            int *Path = NULL;
            int V = 0, AdjV = 0;
            int i = 0;
        
            /************ Distence[]It is used to store the distance from each vertex to the source vertex, and Path [] is used to store the Path************/
            Distence = (ListElementType *)malloc(sizeof(ListElementType)*(G->NV));
            Path = (int *)malloc(sizeof(int)*(G->NV));
        
            /*************************** Initialize distance array********************************/
            for (i = 0; i < G->NV; i++)
            {
                Distence[i].Distance = INT_MAX;//The distance from all vertices (except the source vertex) to the source vertex is initialized to be positive infinity (replaced with int UU max)
                Distence[i].Vertex = -i - 1;//When Distence[].Vertex is negative, vertex i (i = - Vertex - 1) has not found the shortest path to the source vertex
                Path[i] = -1;
            }
            Distence[SourceV].Distance = 0;//The distance from the source vertex to the source vertex is initialized to 0
        
            /****************************** Create a linear table*********************************/
            L = CreateList();
        
            /******************************** Copy all the elements in the sentence [] to the linear table and sort********************************/
            for (i = 0; i < G->NV; i++)
            {
                AddList(L, Distence[i]);
            }
            ListBubbleSort(L);
        
            /********************** Find the shortest path from all vertices to source vertices***********************/
            while (1)
            {
                if (IsListEmpty(L))
                {
                    break;
                }
        
                Temp = DeleteList(L);
                V = -Temp.Vertex - 1;
                Distence[V].Distance = Temp.Distance;//The shortest distance from vertex V to source vertex was found
                Distence[V].Vertex = V;//Indicates that vertex V has found the shortest distance
        
                //All the neighboring vertices of traversing vertex V have not found the shortest path yet
                for (AdjV = 0; AdjV < G->NV; AdjV++)
                {
                    if ((G->G[V][AdjV] != 0) && (Distence[AdjV].Vertex < 0))
                    {
                        //Because the shortest distance from the vertex v to the source vertex is found, the distance from the critical vertex of V to the source vertex may change, check.
                        if (Distence[AdjV].Distance > Distence[V].Distance + G->G[V][AdjV])
                        {
                            Distence[AdjV].Distance = Distence[V].Distance + G->G[V][AdjV];
                            Path[AdjV] = V;
                        }
                    }
                }
        
                //Because of the change of the Distence [], the linear table is empty and the vertices in the Distence [], which do not determine the shortest path, are added to the linear table again and sorted.
                EnListEmpty(L);
                for (i = 0; i < G->NV; i++)
                {
                    if (Distence[i].Vertex < 0)
                    {
                        AddList(L, Distence[i]);
                    }
                }
                ListBubbleSort(L);
            }
        
            //Print shortest path length table
            printf("\nDistence[]: \n");
            for (i = 0; i < G->NV; i++)
            {
                printf("%3d", Distence[i].Distance);
            }
            printf("\n");
            for (i = 0; i < G->NV; i++)
            {
                printf("%3d", Distence[i].Vertex);
            }
        
            //Print shortest path table
            printf("\nPath[]: \n");
            for (i = 0; i < G->NV; i++)
            {
                printf("%3d", Path[i]);
            }
        
        
            //Release space
            DestroyList(L);
            free(Distence);
            free(Path);
        }
        
      3. Operation result

  2. A single source shortest path algorithm for powerless graph
    The weighted graph can be regarded as the weighted graph with each edge weight of 1, so it can still be solved by Dijkstra algorithm.
    In addition, it can be solved by sequence traversal.

    1. Example: find the shortest path length from each vertex to the source vertex v1

    2. PN code description

      void Unweighted(Graph G,Vertex S)
      {
          InsertQueue(Q,S);
          while(!IsQueueEmpty(Q))
          {
              V=DeQueue(Q);
              for(V Every adjacent vertex of W)
              {
                  if(Distence[W]==-1)//If W is visited
                  {
                      Distence[W]=Distence[V]+1;
                      Path[W]=V;
                      InsertQueue(Q,W);
                  }
              }
          }
      }
      
    3. code implementation

      //A single source shortest path algorithm for powerless graph
      void Unweight(MGraph G, Vertex SourceV)
      {
          Queue Q = NULL;
          Vertex V = 0, AdjV = 0;
          int *Distence = NULL, *Path = NULL;
          int i = 0, j = 0;
      
          /************ Distence[]It is used to store the distance from each vertex to the source vertex, and Path [] is used to store the Path************/
          Distence = (int *)malloc(sizeof(int)*(G->NV));
          Path = (int *)malloc(sizeof(int)*(G->NV));
      
          /*************************** Initialize array********************************/
          for (i = 0; i < G->NV; i++)
          {
              Distence[i] = -1;
              Path[i] = -1;
          }
      
          //Create queue
          Q = CreateQueue();
      
          //The distance from the source vertex to the source vertex is 0, and the source vertex is queued
          Distence[SourceV] = 0;
          InsertQueue(Q, SourceV);
      
          //Find the shortest path length and path from each node to the source node
          while (!IsQueueEmpty(Q))
          {
              V = DeleteQueue(Q);//Vertex V out of queue
      
              //Traverse adjacency vertex AdjV of vertex V, and queue adjacency vertices that have not been visited
              for (AdjV = 0; AdjV < G->NV; AdjV++)
              {
                  if (G->G[V][AdjV] != 0 && Distence[AdjV] == -1)//Adjacency vertex of V not visited
                  {
                      Distence[AdjV] = Distence[V] + 1;//Distance from adjacent vertex of V to source vertex = distance from V to source vertex + 1
                      Path[AdjV] = V;//Adjacency vertex of V in the path from AdjV to source vertex, the last vertex of AdjV is v
                      InsertQueue(Q, AdjV);//V's adjacency vertices are queued
                  }
              }
          }
      
          //Output two arrays
          printf("Distence[]=\n");
          for (i = 0; i < G->NV; i++)
          {
              printf("%d ", Distence[i]);
          }
      
          printf("\nPath[]=\n");
          for (i = 0; i < G->NV; i++)
          {
              printf("%d ", Path[i]);
          }
      
          //Free space for application
          DestroyQueue(Q);
          free(Distence);
          free(Path);
      
      }
      
    4. Operation result

Multi source shortest path algorithm

The so-called multi-source shortest path problem is to find the shortest path between the vertices of a graph.

  1. Multi shortest path algorithm of weighted graph

    1. Method 1: for n vertices, each vertex is regarded as the source vertex, and Dijstra algorithm is used.
    2. Method 2: Floyd algorithm
      1. Steps:

        1. I \ rightarrow \ {v| V < v_k, and v \in V\} \rightarrow v_j \}Dk[i][j] = the minimum length of path {vi → {V ∣ V < v k, and V ∈ V} → vj}; D − 1D {- 1} D − 1 is the minimum length of figure GGG Adjacency matrix.
        2. Know Dk − 1D^{k-1}Dk − 1, and deduce the steps of DkD^kDk:
          • I] [J] = DK − 1[i][j]D^k[i][j]=D^{k-1}[i][j]Dk[i][j]=Dk − 1[i][j];

          • Short path composition: Dk[i][j]=Dk − 1[i][k]+Dk − 1[k][j]D^k[i][j]=D^{k-1}[i][k]+D^{k-1}[k][j]Dk[i][j]=Dk − 1[i][k]+Dk − 1[k][j]

            therefore
            Dk[i][j]=min{Dk−1[i][j],Dk−1[i][k]+Dk−1[k][j]} D^k[i][j]=min\{ D^{k-1}[i][j],D^{k-1}[i][k]+D^{k-1}[k][j]\} Dk[i][j]=min{Dk−1[i][j],Dk−1[i][k]+Dk−1[k][j]}

        3. From the rule of the second step, we can deduce from D − 1D^{-1}D − 1 step by step to D ∣ V ∣ 1D ^ {V ゗ 1} D ∣ V ∣ 1;
        4. D ∣ V ∣ 1[i][j] d ^ {V ゗ 1} [i] [J] d ∣ V ∣ - 1[i][j] is the shortest path from vertex VIV ∣ IVI to vertex vjv ∣ jvj.
      2. PN code description

        void Floyd()
        {
            //Initialize array
            for(i=0;i<N;i++)
            {
                for(j=0;j<N;j++)
                {
                    D[i][j]=G[i][j];
                    Path[i][j]=-1;
                }
            }
        
            //From D(-1) to D(|V|-1)
            for(k=0;k<N;k++)
            {
                for(i=0;i<N;i++)
                {
                    for(j=0;j<N;j++)
                    {
                        D[i][j]=min{D[i][j],D[i][k]+D[k][j]};
                        Path[i][j]=k;
                    }
                }
            }
        }
        
      3. code implementation

        //Multi source shortest path algorithm for weighted graph
        void Floyd(MGraph G)
        {
            WeightType **D = NULL, **Path = NULL;
            int i = 0, j = 0, k = 0;
        
            /*************************** Request space for distance array D*********************************/
            D = (WeightType**)malloc(sizeof(WeightType*)*(G->NV));
            D[0] = (WeightType*)malloc(sizeof(WeightType)*(G->NV*G->NV));
            for (i = 1; i < G->NV; i++)
            {
                D[i] = &(D[0][i*G->NV]);
            }
        
            /**************************** Request space for Path array Path*******************************/
            Path = (WeightType**)malloc(sizeof(WeightType*)*(G->NV));
            Path[0] = (WeightType*)malloc(sizeof(WeightType)*(G->NV*G->NV));
            for (i = 1; i < G->NV; i++)
            {
                Path[i] = &(Path[0][i*G->NV]);
            }
        
            /******************************* Initialize array*********************************/
            for (i = 0; i < G->NV; i++)
            {
                for (j = 0; j < G->NV; j++)
                {
                    D[i][j] = G->G[i][j];
                    Path[i][j] = -1;
                }
            }
        
            /***************************** Floyd Algorithm*******************************/
            for (k = 0; k < G->NV; k++)
            {
                for (i = 0; i < G->NV; i++)
                {
                    for (j = 0; j < G->NV; j++)
                    {
                        //Because of this comparison, when the adjacency matrix of graph G is initialized, there is no Vertex connected by edges, which is represented by positive infinity
                        if (D[i][k] + D[k][j] < D[i][j])
                        {
                            D[i][j] = D[i][k] + D[k][j];
                            Path[i][j] = k;
                        }
                    }
                }
            }
        
            /************************** Print two arrays***************************/
            printf("\nD(k):\n");
            PrintTwoDimensionalArray(D, G->NV, G->NV);
            printf("\nPath[]:\n");
            PrintTwoDimensionalArray(Path, G->NV, G->NV);
        
            /***************************** Freeing 2D array space******************************/
            free(D[0]);
            free(D);
            free(Path[0]);
            free(Path);
        }
        
      4. Operation result

        Where 1073741823 represents positive infinity and no path.

  2. Multi-source shortest path algorithm for graph with no right
    The weighted graph can be regarded as the weighted graph with each edge weight of 1, so it can still be solved by Freud algorithm.

Published 15 original articles, won praise 3, visited 1015
Private letter follow

Posted on Mon, 10 Feb 2020 05:48:42 -0800 by srfdriver22