อัลกอริทึมของ Dijkstra (หรืออัลกอริธึม Shortest Path First ของ Dijkstra, อัลกอริธึม SPF) เป็นอัลกอริธึมในการค้นหาเส้นทางที่สั้นที่สุดระหว่างโหนดต่างๆ ในกราฟ ซึ่งอาจเป็นตัวแทนของเครือข่ายถนน เป็นต้น อัลกอริธึมสร้างแผนผังของเส้นทางที่สั้นที่สุดจากจุดยอดเริ่มต้น แหล่งที่มา ไปยังจุดอื่นๆ ทั้งหมดในกราฟ
อัลกอริทึมของ Dijkstra ค้นหาแผนผังเส้นทางที่สั้นที่สุดจากโหนดต้นทางเดียว โดยการสร้างชุดโหนดที่มีระยะห่างน้อยที่สุดจากแหล่งที่มา
กราฟมีดังต่อไปนี้−
-
จุดยอดหรือโหนดที่แสดงในอัลกอริทึมโดย v หรือ u
-
ขอบถ่วงน้ำหนักที่เชื่อมต่อสองโหนด:(u,v) หมายถึงขอบและ w(u,v) หมายถึงน้ำหนักของมัน ในแผนภาพด้านขวา น้ำหนักของแต่ละขอบจะเขียนเป็นสีเทา
ขั้นตอนอัลกอริทึม
- กำหนดระยะจุดยอดทั้งหมด =อินฟินิตี้ ยกเว้นจุดยอดต้นทาง กำหนดระยะต้นทาง =0
- ดันจุดยอดต้นทางในคิวที่มีลำดับความสำคัญขั้นต่ำในรูปแบบ (ระยะทาง จุดยอด) เนื่องจากการเปรียบเทียบในคิวที่มีลำดับความสำคัญขั้นต่ำจะเป็นไปตามระยะทางของจุดยอด
- จุดยอดจุดยอดด้วยระยะห่างขั้นต่ำจากคิวลำดับความสำคัญ (ในตอนแรก จุดยอดที่ผุดขึ้น =ต้นทาง)
- อัปเดตระยะทางของจุดยอดที่เชื่อมต่อไปยังจุดยอดที่แตกในกรณีที่ "ระยะจุดยอดปัจจุบัน + น้ำหนักขอบ <ระยะจุดยอดถัดไป" จากนั้นดันจุดยอดที่มีระยะทางใหม่ไปยังคิวลำดับความสำคัญ
- หากเคยไปถึงจุดยอดที่โผล่มาแล้ว ให้ดำเนินการต่อโดยไม่ใช้จุดยอดนั้น
- ใช้อัลกอริทึมเดิมอีกครั้งจนกว่าคิวลำดับความสำคัญจะว่างเปล่า
จากกราฟและจุดยอดต้นทางในกราฟ ให้ค้นหาเส้นทางที่สั้นที่สุดจากต้นทางไปยังจุดยอดทั้งหมดในกราฟที่กำหนด ให้ G[][] เมทริกซ์ของน้ำหนักกราฟ n ไม่มีจุดยอดในกราฟ u โหนดเริ่มต้น
อินพุต
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
คำอธิบาย
-
สร้างเมทริกซ์ต้นทุน C[ ][ ] จากเมทริกซ์ที่อยู่ติดกัน adj[ ][ ] C[i][j] คือค่าใช้จ่ายในการเปลี่ยนจากจุดยอด i ไปยังจุดยอด j หากไม่มีขอบระหว่างจุดยอด i และ j แล้ว C[i][j] จะเป็นอนันต์
-
Array ที่เยี่ยมชม[ ] ถูกกำหนดค่าเริ่มต้นให้เป็นศูนย์
for(i=0;i<n;i++) visited[i]=0;
-
หากจุดยอด 0 คือจุดยอดต้นทาง การเข้าชม[0] จะถูกทำเครื่องหมายเป็น 1
-
สร้างเมทริกซ์ระยะทาง โดยเก็บต้นทุนของจุดยอดจากจุดยอด 0 ถึง n-1 จากจุดยอดต้นทาง 0
for(i=1;i<n;i++) distance[i]=cost[0][i];
เริ่มแรก ระยะทางของจุดยอดต้นทางจะเป็น 0 เช่น Distance[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);
}
} 