ডিকস্ট্রার অ্যালগরিদম একটি গ্রাফে সোর্স নোড থেকে অন্যান্য সব নোড পর্যন্ত শর্টেস্ট পাথ বের করে। এখানে গ্রাফটি অ্যাডজেসেন্সি ম্যাট্রিক্স (কস্ট ম্যাট্রিক্স) দিয়ে রিপ্রেজেন্ট করা হয়েছে।
কমপ্লেক্সিটি
- অ্যাডজেসেন্সি ম্যাট্রিক্স রিপ্রেজেন্টেশনের জন্য: O(V²) যেখানে V = নোড সংখ্যা।
ইনপুট এবং আউটপুট
Output:
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)
Input: নোড সংখ্যা n, ডিস্ট্যান্স লিস্ট, नेक्स্ট লিস্ট, স্টার্ট ভার্টেক্স
Output: স্টার্ট থেকে সব নোড পর্যন্ত শর্টেস্ট পাথ
Begin
status[u] := unconsidered for all u
dist[u] := cost matrix থেকে সোর্স থেকে দূরত্ব
next[u] := start
status[start] := considered, dist[start] := 0, next[start] := null
while unconsidered vertex u with minimum distance exists:
status[u] := considered
for all v in V:
if status[v] == unconsidered AND dist[v] > dist[u] + cost[u,v]:
dist[v] := dist[u] + cost[u,v]
next[v] := u
done
done
End
C++ উদাহরণ
#include <iostream>
#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 min = INF, index = -1;
for(int i=0; i -1) {
status[u]=2;
for(int v=0; v dist[u] + costMat[u][v]) {
dist[v] = dist[u] + costMat[u][v];
next[v] = u;
}
}
}
int main() {
int dis[V], next[V], start=0;
dijkstra(V, dis, next, start);
for(int i=0; i আউটপুট
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
