Thuật toán Dijkstra (hoặc thuật toán Đường dẫn ngắn nhất Dijkstra, thuật toán SPF) là một thuật toán để tìm đường đi ngắn nhất giữa các nút trong một biểu đồ, có thể biểu diễn, ví dụ, mạng lưới đường. Thuật toán tạo một cây gồm các đường đi ngắn nhất từ đỉnh bắt đầu, nguồn, đến tất cả các điểm khác trong biểu đồ.
Thuật toán của Dijkstra tìm cây đường dẫn ngắn nhất từ một nút nguồn duy nhất, bằng cách xây dựng một tập hợp các nút có khoảng cách tối thiểu từ nguồn.
Biểu đồ có như sau−
-
đỉnh hoặc nút, được biểu thị trong thuật toán bằng v hoặc u.
-
các cạnh có trọng số nối hai nút:(u, v) biểu thị một cạnh và w (u, v) biểu thị trọng lượng của nó. Trong biểu đồ bên phải, trọng số của mỗi cạnh được viết bằng màu xám.
Các bước thuật toán
- Đặt khoảng cách tất cả các đỉnh =infinity ngoại trừ đỉnh nguồn, đặt khoảng cách nguồn =0.
- Đẩy đỉnh nguồn vào hàng đợi ưu tiên tối thiểu ở dạng (khoảng cách, đỉnh), vì so sánh trong hàng đợi ưu tiên tối thiểu sẽ theo khoảng cách các đỉnh.
- Đánh dấu đỉnh với khoảng cách tối thiểu so với hàng đợi ưu tiên (lúc đầu, đỉnh đã xuất hiện =nguồn).
- Cập nhật khoảng cách của các đỉnh được kết nối với đỉnh được bật trong trường hợp "khoảng cách đỉnh hiện tại + trọng số cạnh
- Nếu đỉnh đã bật đã được truy cập trước đó, chỉ cần tiếp tục mà không sử dụng nó.
- Áp dụng lại cùng một thuật toán cho đến khi hàng đợi ưu tiên trống.
Cho một đồ thị và một đỉnh nguồn trong đồ thị, hãy tìm đường đi ngắn nhất từ nguồn đến tất cả các đỉnh trong đồ thị đã cho. Cho trước ma trận G [] [] có trọng số đồ thị, không có đỉnh nào trong đồ thị, u nút bắt đầu.
Đầu vào
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 Đầu ra
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
Giải thích
-
Tạo ma trận chi phí C [] [] từ ma trận kề adj [] []. C [i] [j] là chi phí đi từ đỉnh i đến đỉnh j. Nếu không có cạnh nào giữa các đỉnh i và j thì C [i] [j] là vô cùng.
-
Mảng đã truy cập [] được khởi tạo bằng 0.
for(i=0;i<n;i++) visited[i]=0;
-
Nếu đỉnh 0 là đỉnh nguồn thì đã thăm [0] được đánh dấu là 1.
-
Tạo ma trận khoảng cách, bằng cách lưu trữ chi phí của các đỉnh từ đỉnh no. 0 đến n-1 từ đỉnh nguồn 0.
for(i=1;i<n;i++) distance[i]=cost[0][i];
Ban đầu, khoảng cách của đỉnh nguồn được coi là 0. tức là khoảng cách [0] =0;
for(i=1;i<n;i++) visited[i]=0;
-
Chọn một đỉnh w, sao cho khoảng cách [w] là nhỏ nhất và số lượt truy cập [w] là 0. Đánh dấu đã thăm [w] là 1.
-
Tính toán lại khoảng cách ngắn nhất của các đỉnh còn lại từ nguồn.
-
Chỉ, các đỉnh không được đánh dấu là 1 trong mảng đã thăm [] mới nên được xem xét để tính toán lại khoảng cách. tức là đối với mỗi đỉnh v
if(visited[v]==0) distance[v]=min(distance[v], distance[w]+cost[w][v])
Ví dụ
#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);
}
}