সিঙ্গেল-সোর্স শর্টেস্ট পাথস, নন-নেগেটিভ ওয়েটস (ডিকস্ট্রা)

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

স্টার্টিং নোড থেকে অন্য যেকোনো নোড পর্যন্ত সবচেয়ে ছোট ডিস্ট্যান্স বের করা হয়। এই সমস্যায় গ্রাফ অ্যাডজেসেন্সি ম্যাট্রিক্স দিয়ে রিপ্রেজেন্ট করা হয়। (কস্ট ম্যাট্রিক্স এবং অ্যাডজেসেন্সি ম্যাট্রিক্স এই উদ্দেশ্যে একই)।

ইনপুট − অ্যাডজেসেন্সি ম্যাট্রিক্স −

0 3 6 ∞ ∞ ∞ ∞
3 0 2 1 ∞ ∞ ∞
6 2 0 1 4 2 ∞
∞ 1 1 0 2 ∞ 4
∞ ∞ 4 2 0 2 1
∞ ∞ 2 ∞ 2 0 1
∞ ∞ ∞ 4 1 1 0

আউটপুট −

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

অ্যালগরিদম

dijkstraShortestPath(n, dist, next, start)

ইনপুট − টোটাল নোড n, প্রতিটি ভার্টেক্সের ডিস্ট্যান্স লিস্ট, কোন নোড পরবর্তী আসবে সেটা সংরক্ষণ করার next লিস্ট, এবং সিড বা স্টার্ট ভার্টেক্স।

আউটপুট − স্টার্ট থেকে সব অ্যান্য ভার্টেক্স পর্যন্ত শর্টেস্ট পাথ।

Begin
    create a status list to hold the current status of the selected node
    for all vertices u in V do
        status[u] := unconsidered
        dist[u] := distance from source using cost matrix
        next[u] := start
    done
    status[start] := considered, dist[start] := 0 and next[start] := φ
    while take unconsidered vertex u as distance is minimum do
        status[u] := considered
        for all vertex v in V do
            if status[v] = unconsidered then
                if dist[v] > dist[u] + cost[u,v] then
                    dist[v] := dist[u] + cost[u,v]
                    next[v] := u
                done
            done
        done
End

উদাহরণ (C++)

#include 
#define V 7
#define INF 999
using namespace std;
int costMat[V][V] = {
    {0, 3, 6, INF, INF, INF, INF},
    {3, 0, 2, 1, INF, INF, INF},
    {6, 2, 0, 1, 4, 2, INF},
    {INF, 1, 1, 0, 2, INF, 4},
    {INF, INF, 4, 2, 0, 2, 1},
    {INF, INF, 2, INF, 2, 0, 1},
    {INF, INF, INF, 4, 1, 1, 0}
};
int minimum(int *status, int *dis, int n){
    int i, min, index;
    min = INF;
    for(i = 0; i < n; i++)
        if(dis[i] < min && status[i] == 1){
            min = dis[i];
            index = i;
        }
    if(status[index] == 1)
        return index;
    else
        return -1;
}
void dijkstra(int n, int *dist,int *next, int s){
    int status[V];
    int u, v;
    for(u = 0; u < n; u++){
        status[u] = 1;
        dist[u] = costMat[u][s];
        next[u] = s;
    }
    status[s] = 2; dist[s] = 0; next[s] = -1;
    while((u = minimum(status, dist, n)) > -1){
        status[u] = 2;
        for(v = 0; v < n; v++)
            if(status[v] == 1)
                if(dist[v] > dist[u] + costMat[u][v]){
                    dist[v] = dist[u] + costMat[u][v];
                    next[v] = u;
                }
    }
}
int main(){
    int dis[V], next[V], i, start = 0;
    dijkstra(V, dis, next, start);
    for(i = 0; i < V; i++)
        if(i != start)
            cout << start << " to " << i << ", Using: " << next[i] << ", Cost: " << dis[i] << endl;
}

আউটপুট

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