อัลกอริทึมของ Dijkstra สำหรับการเป็นตัวแทนรายการ Adjacency

มีกราฟ G(V, E) ที่กำหนดพร้อมการแสดงรายการที่อยู่ติดกัน และให้จุดยอดต้นทางด้วย อัลกอริทึมของ Dijkstra เพื่อค้นหาเส้นทางที่สั้นที่สุดระหว่างจุดยอดต้นทางไปยังจุดยอดอื่นๆ ของกราฟ G

เพื่อแก้ปัญหานี้ เราจะใช้สองรายการ หนึ่งคือการจัดเก็บจุดยอดที่ถือว่าเป็นต้นไม้เส้นทางที่สั้นที่สุด และอีกจุดหนึ่งจะเก็บจุดยอดที่ยังไม่ได้พิจารณา ในแต่ละขั้นตอนของอัลกอริทึม เราจะพบจุดยอดที่ยังไม่ได้พิจารณาและมีระยะห่างน้อยที่สุดจากแหล่งกำเนิด

รายการอื่นใช้เพื่อเก็บโหนดก่อนหน้า เมื่อใช้โหนดก่อนหน้า เราจะสามารถค้นหาเส้นทางจากต้นทางและปลายทางได้

ความซับซ้อนของอัลกอริธึมเส้นทางที่สั้นที่สุดของ Dijkstra คือ O(E log V) เนื่องจากกราฟแสดงโดยใช้รายการที่อยู่ติดกัน . โดยที่ E คือจำนวนขอบ และ V คือจำนวนจุดยอด

อินพุตและเอาต์พุต

Input:
The adjacency list of the graph with the cost of each edge.

Output:
0 to 1, Cost: 3 Previous: 0
0 to 2, Cost: 5 Previous: 1
0 to 3, Cost: 4 Previous: 1
0 to 4, Cost: 6 Previous: 3
0 to 5, Cost: 7 Previous: 2
0 to 6, Cost: 7 Previous: 4

อัลกอริทึม

dijkstraShortestPath(g : Graph, dist, prev, start : node)

ป้อนข้อมูล - กราฟ g รายการ dist สำหรับเก็บระยะทาง รายการก่อนหน้าสำหรับโหนดรุ่นก่อน และเริ่มจุดยอด

ผลลัพธ์ − เส้นทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังจุดยอดอื่นทั้งหมด

Begin
   for all vertices u in (V - start) do
      dist[u] := ∞
      prev[u] := φ
   done

   set dist[start] = 0 and prev[start] := φ

   for all node u in V do
      insert u into queue ‘Q’.
   done

   while Q is not empty do
      u := minimum element from Queue
      delete u from Q
      insert u into set S

      for each node v adjacent with node u do
         if dist[u]+cost(v) < dist[v] then
            dist[v] := dist[u]+cost(v)
            prev[v] := u
      done
   done
End

ตัวอย่าง

#include<iostream>
#include<set>
#include<list>
#include<algorithm>
using namespace std;

typedef struct nodes {
   int dest;
   int cost;
}node;

class Graph {
   int n;
   list<node> *adjList;
   private:
      void showList(int src, list<node> lt) {
         list<node> :: iterator i;
         node tempNode;

         for(i = lt.begin(); i != lt.end(); i++) {
            tempNode = *i;
            cout << "(" << src << ")---("<<tempNode.dest << "|"<<tempNode.cost<<") ";
         }
         cout << endl;
      }
   public:
      Graph() {
         n = 0;
      }

      Graph(int nodeCount) {
         n = nodeCount;
         adjList = new list<node>[n];
      }

      void addEdge(int source, int dest, int cost) {
         node newNode;
         newNode.dest = dest;
         newNode.cost = cost;
         adjList[source].push_back(newNode);
      }

      void displayEdges() {
         for(int i = 0; i<n; i++) {
            list<node> tempList = adjList[i];
            showList(i, tempList);
         }
      }

      friend void dijkstra(Graph g, int *dist, int *prev, int start);
};

void dijkstra(Graph g, int *dist, int *prev, int start) {
   int n = g.n;

   for(int u = 0; u<n; u++) {
      dist[u] = 9999;   //set as infinity
      prev[u] = -1;    //undefined previous
   }

   dist[start] = 0;   //distance of start is 0
   set<int> S;       //create empty set S
   list<int> Q;

   for(int u = 0; u<n; u++) {
      Q.push_back(u);    //add each node into queue
   }

   while(!Q.empty()) {
      list<int> :: iterator i;
      i = min_element(Q.begin(), Q.end());
      int u = *i; //the minimum element from queue
      Q.remove(u);
      S.insert(u); //add u in the set
      list<node> :: iterator it;

      for(it = g.adjList[u].begin(); it != g.adjList[u].end();it++) {
         if((dist[u]+(it->cost)) < dist[it->dest]) { //relax (u,v)
            dist[it->dest] = (dist[u]+(it->cost));
            prev[it->dest] = u;
         }
      }
   }
}

main() {
   int n = 7;
   Graph g(n);
   int dist[n], prev[n];
   int start = 0;

   g.addEdge(0, 1, 3);
   g.addEdge(0, 2, 6);
   g.addEdge(1, 0, 3);
   g.addEdge(1, 2, 2);
   g.addEdge(1, 3, 1);
   g.addEdge(2, 1, 6);
   g.addEdge(2, 1, 2);
   g.addEdge(2, 3, 1);
   g.addEdge(2, 4, 4);

   g.addEdge(2, 5, 2);
   g.addEdge(3, 1, 1);
   g.addEdge(3, 2, 1);
   g.addEdge(3, 4, 2);
   g.addEdge(3, 6, 4);
   g.addEdge(4, 2, 4);
   g.addEdge(4, 3, 2);
   g.addEdge(4, 5, 2);
   g.addEdge(4, 6, 1);
   g.addEdge(5, 2, 2);
   g.addEdge(5, 4, 2);
   g.addEdge(5, 6, 1);
   g.addEdge(6, 3, 4);
   g.addEdge(6, 4, 1);
   g.addEdge(6, 5, 1);

   dijkstra(g, dist, prev, start);

   for(int i = 0; i<n; i++)
      if(i != start)
         cout<<start<<" to "<<i<<", Cost: "<<dist[i]<<" Previous: "<<prev[i]<<endl;
}

ผลลัพธ์

0 to 1, Cost: 3 Previous: 0
0 to 2, Cost: 5 Previous: 1
0 to 3, Cost: 4 Previous: 1
0 to 4, Cost: 6 Previous: 3
0 to 5, Cost: 7 Previous: 2
0 to 6, Cost: 7 Previous: 4