โปรแกรม C++ เพื่อใช้อัลกอริทึมของ Dijkstra โดยใช้ Set

นี่คือโปรแกรม C ++ เพื่อใช้อัลกอริทึมของ Dijkstra โดยใช้ Set ที่นี่เราต้องการสองชุด เราสร้างแผนผังเส้นทางที่สั้นที่สุดโดยมีโหนดต้นทางที่กำหนดเป็นรูท ชุดหนึ่งประกอบด้วยจุดยอดที่รวมอยู่ในแผนผังเส้นทางที่สั้นที่สุด และชุดอื่นๆ ประกอบด้วยจุดยอดที่ยังไม่รวมอยู่ในแผนผังเส้นทางที่สั้นที่สุด ในทุกขั้นตอน เราจะพบจุดยอดซึ่งอยู่อีกชุดหนึ่ง (ชุดที่ยังไม่ได้รวมไว้) และมีระยะห่างน้อยที่สุดจากแหล่งกำเนิด

อัลกอริทึม:

Begin
   function dijkstra() to find minimum distance:
   1) Create a set Set that keeps track of vertices included in shortest
   path tree, Initially, the set is empty.
   2) A distance value is assigned to all vertices in the input graph.
   Initialize all distance values as INFINITE. Distance value is assigned as
   0 for the source vertex so that it is picked first.
   3) While Set doesn’t include all vertices
      a) Pick a vertex u which is not there in the Set and has minimum distance value.
      b) Include u to Set.
      c) Distance value is updated of all adjacent vertices of u.
      For updating the distance values, iterate through all adjacent
      vertices. if sum of distance value of u (from source) and weight of
      edge u-v for every adjacent vertex v, is less than the distance value
      of v, then update the distance value of v.
End

โค้ดตัวอย่าง

#include <iostream>
#include <climits>
#include <set>
using namespace std;
#define N 5
int minDist(int dist[], bool Set[])//calculate minimum distance
{
   int min = INT_MAX, min_index;
   for (int v = 0; v < N; v++)
   if (Set[v] == false && dist[v] <= min)
   min = dist[v], min_index = v;
   return min_index;
}
int printSol(int dist[], int n)//print the solution
{
   cout<<"Vertex Distance from Source\n";
   for (int i = 0; i < N; i++)
   cout<<" \t\t \n"<< i<<" \t\t "<<dist[i];
}
void dijkstra(int g[N][N], int src)
{
   int dist[N];
   bool Set[N];
   for (int i = 0; i < N; i++)
   dist[i] = INT_MAX, Set[i] = false;
   dist[src] = 0;
   for (int c = 0; c < N- 1; c++)
   {
      int u = minDist(dist, Set);
      Set[u] = true;
      for (int v = 0; v < N; v++)
      if (!Set[v] && g[u][v] && dist[u] != INT_MAX && dist[u]
         + g[u][v] < dist[v])
         dist[v] = dist[u] + g[u][v];
   }
   printSol(dist, N);
}
int main()
{
   int g[N][N] = { { 0, 4, 0, 0, 0 },
      { 4, 0, 7, 0, 0 },
      { 0, 8, 0, 9, 0 },
      { 0, 0, 7, 0, 6 },
      { 0, 2, 0, 9, 0 }};
   dijkstra(g, 0);
   return 0;
}

ผลลัพธ์

Vertex Distance from Source
0 0
1 4
2 11
3 20
4 26