दिज्क्स्ट्रा का एल्गोरिथम (या डिजस्ट्रा का शॉर्टेस्ट पाथ फर्स्ट एल्गोरिथम, SPF एल्गोरिथम) ग्राफ में नोड्स के बीच सबसे छोटा पथ खोजने के लिए एक एल्गोरिदम है, जो उदाहरण के लिए, सड़क नेटवर्क का प्रतिनिधित्व कर सकता है। एल्गोरिथम शुरुआती शीर्ष, स्रोत से लेकर ग्राफ़ के अन्य सभी बिंदुओं तक सबसे छोटे रास्तों का एक ट्री बनाता है।
दिज्क्स्ट्रा का एल्गोरिदम स्रोत से न्यूनतम दूरी वाले नोड्स का एक सेट बनाकर, एकल स्रोत नोड से सबसे छोटा पथ वृक्ष ढूंढता है।
ग्राफ़ में निम्नलिखित हैं-
-
एल्गोरिथम में वर्टिस, या नोड्स, को v या u द्वारा दर्शाया जाता है।
-
भारित किनारे जो दो नोड्स को जोड़ते हैं:(यू, वी) एक किनारे को दर्शाता है, और डब्ल्यू (यू, वी) इसके वजन को दर्शाता है। दाईं ओर दिए गए आरेख में, प्रत्येक किनारे का भार धूसर रंग में लिखा गया है।
एल्गोरिदम चरण
- स्रोत शीर्ष को छोड़कर सभी शीर्ष दूरी =अनंत सेट करें, स्रोत दूरी =0 सेट करें।
- स्रोत के शीर्ष को फ़ॉर्म (दूरी, शीर्ष) में एक न्यूनतम-प्राथमिकता कतार में पुश करें, क्योंकि न्यूनतम-प्राथमिकता कतार में तुलना कोने की दूरी के अनुसार होगी।
- प्राथमिकता कतार से न्यूनतम दूरी के साथ शीर्ष को पॉप करें (पहले पॉप किया गया शीर्ष =स्रोत)।
- "वर्तमान शीर्ष दूरी + किनारे का भार <अगले शीर्ष दूरी" के मामले में कनेक्ट किए गए शीर्षों की दूरी को पॉप किए गए शीर्ष पर अपडेट करें, फिर शीर्ष को नई दूरी के साथ प्राथमिकता कतार में धकेलें।
- यदि पॉप किए गए शीर्ष को पहले देखा गया है, तो इसका उपयोग किए बिना जारी रखें।
- प्राथमिकता कतार खाली होने तक वही एल्गोरिदम फिर से लागू करें।
ग्राफ़ में एक ग्राफ़ और एक स्रोत शीर्ष को देखते हुए, दिए गए ग्राफ़ में स्रोत से सभी शीर्षों तक के सबसे छोटे पथ खोजें। ग्राफ वजन के G[][] मैट्रिक्स को देखते हुए, ग्राफ में शीर्ष की संख्या, आप नोड शुरू कर रहे हैं।
इनपुट
G[max][max]={{0,1,0,3,10},
{1,0,5,0,0},
{0,5,0,2,1},
{3,0,2,0,6},
{10,0,1,6,0}}
n=5
u=0 आउटपुट
Distance of node1=1 Path=1<-0 Distance of node2=5 Path=2<-3<-0 Distance of node3=3 Path=3<-0 Distance of node4=6 Path=4<-2<-3<-0
स्पष्टीकरण
-
आसन्न मैट्रिक्स adj[ ][ ] से कॉस्ट मैट्रिक्स C[ ][ ] बनाएं। C[i][j] शीर्ष i से शीर्ष j तक जाने की लागत है। यदि शीर्ष i और j के बीच कोई किनारा नहीं है तो C[i][j] अनंत है।
-
देखी गई सरणी[ ] को शून्य से प्रारंभ किया गया है।
for(i=0;i<n;i++) visited[i]=0;
-
यदि शीर्ष 0 स्रोत शीर्ष है तो विज़िट किया गया [0] 1 के रूप में चिह्नित है।
-
शीर्ष संख्या से कोने की लागत को संग्रहीत करके दूरी मैट्रिक्स बनाएं। स्रोत शीर्ष 0 से 0 से n-1.
for(i=1;i<n;i++) distance[i]=cost[0][i];
प्रारंभ में, स्रोत शीर्ष की दूरी को 0. यानी दूरी[0]=0;
. के रूप में लिया जाता हैfor(i=1;i<n;i++) visited[i]=0;
-
एक शीर्ष w चुनें, जैसे कि दूरी [w] न्यूनतम हो और देखी गई [w] 0 हो। विज़िट किए गए [w] को 1 के रूप में चिह्नित करें।
-
स्रोत से शेष शीर्षों की न्यूनतम दूरी की पुनर्गणना करें।
-
केवल, देखे गए सरणी में 1 के रूप में चिह्नित नहीं किए गए शीर्षों पर दूरी की पुनर्गणना के लिए विचार किया जाना चाहिए। यानी प्रत्येक शीर्ष v
. के लिए
if(visited[v]==0) distance[v]=min(distance[v], distance[w]+cost[w][v])
उदाहरण
#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
int n=5;
int u=0;
dijkstra(G,n,u);
return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
int cost[max][max],distance[max],pred[max];
int visited[max],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
for(i=0;i<n;i++) {
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1) {
mindistance=INFINITY;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i]) {
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i]) {
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=startnode) {
cout<<"\nDistance of node"<<i<<"="<<distance[i];
cout<<"\nPath="<<i;
j=i;
do {
j=pred[j];
cout<<"<-"<<j;
}while(j!=startnode);
}
}