অ্যাডজেসেন্সি লিস্ট রিপ্রেজেন্টেশনের জন্য ডিকস্ট্রার অ্যালগরিদম

গ্রাফ G(V, E) অ্যাডজেসেন্সি লিস্ট হিসেবে দেওয়া থাকলে ডিকস্ট্রার অ্যালগরিদম ব্যবহার করে সোর্স থেকে সব নোড পর্যন্ত শর্টেস্ট পাথ বের করা যায়। অ্যাডজেসেন্সি লিস্টে কমপ্লেক্সিটি O(E log V)।

ইনপুট এবং আউটপুট

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, dist, prev, start)
Input: গ্রাফ g, dist লিস্ট, prev লিস্ট, সোর্স ভার্টেক্স
Output: শর্টেস্ট পাথসমূহ

Begin
    for all u in V: dist[u]=INF, prev[u]=null
    dist[start]=0, prev[start]=null
    সব নোড Q কিউতে ইনসার্ট করুন
    while Q not empty:
        u = Q থেকে মিনিমাম ডিস্ট্যান্সের নোড
        Q থেকে u ডিলিট, S-এ ইনসার্ট
        for each v adjacent to u:
            if dist[u] + cost(u,v) < dist[v]:
                dist[v] = dist[u] + cost(u,v)
                prev[v] = u
        done
    done
End

C++ উদাহরণ

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

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

class Graph {
    int n; list<node> *adjList;
public:
    Graph(int nc=0) : n(nc) { if(nc) adjList = new list<node>[n]; }
    void addEdge(int s, int d, int c) { adjList[s].push_back({d,c}); }
    friend void dijkstra(Graph, int*, int*, int);
};

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

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