Thuật toán tìm đường đi ngắn nhất Dijkstra
Với bài toán tìm đường đi ngắn nhất, chúng ta có một số thuật toán nổi tiếng giải quyết nó như: Dijkstra hay Floyd.
Thuật toán Dijkstra có 2 loại là:
- Tìm đường đi ngắn nhất từ 1 đỉnh nguồn tới 1 đỉnh đích.
- Tìm đường đi ngắn nhất từ 1 đỉnh nguồn tới các đỉnh còn lại của đồ thị.
Dưới đây là code minh họa cho loại thứ 1 của thuật toán Dijkstra.
#include<iostream>
#include<conio.h>
using namespace std;
#define MAX 50
#define TRUE 1
#define FALSE 0
#define VOCUNG 10000000
int n; //số đỉnh của đồ thị.
int s; //đỉnh đầu.
int t; //đỉnh cuối
char chon;
int truoc[MAX]; //mảng đánh dấu đường đi.
int d[MAX]; //mảng đánh dấu khoảng cách.
int Matrix[MAX][MAX]; //ma trận trọng số
int chuaxet[MAX]; //mảng đánh dấu đỉnh đã được gán nhãn.
void Init(void) {
freopen("DIJKSTRA.IN", "r", stdin);
cin >> n;
cout << "So dinh : " << n << endl;
cin >> s >> t; //nhập đỉnh đầu và đỉnh cuối của đồ thị.
//nhập ma trận của đồ thị.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> Matrix[i][j];
if (Matrix[i][j] == 0) Matrix[i][j] = VOCUNG;
}
}
}
void Result(void) {
cout << "Duong di ngan nhat tu " << (char)(s + 'A' - 1) << " den " << (char)(t + 'A' - 1) << " la" << endl;
cout << (char)(t + 'A' - 1) << "<="; //in đỉnh cuối dưới dạng char.
int i = truoc[t];
while (i != s) {
cout << (char)(i + 'A' - 1) << "<="; //in ra kết quả dưới dạng char.
i = truoc[i];
}
cout << (char)(s + 'A' - 1); //in đỉnh đầu dưới dạng char.
cout << endl << "Do dai duong di la : " << d[t];
}
void Dijkstra(void) {
int u, minp;
//khởi tạo nhãn tạm thời cho các đỉnh.
for (int v = 1; v <= n; v++) {
d[v] = Matrix[s][v];
truoc[v] = s;
chuaxet[v] = FALSE;
}
truoc[s] = 0;
d[s] = 0;
chuaxet[s] = TRUE;
//bươc lặp
while (!chuaxet[t]) {
minp = VOCUNG;
//tìm đỉnh u sao cho d[u] là nhỏ nhất
for (int v = 1; v <= n; v++) {
if ((!chuaxet[v]) && (minp > d[v])) {
u = v;
minp = d[v];
}
}
chuaxet[u] = TRUE; // u la dinh co nhan tam thoi nho nhat
if (!chuaxet[t]) {
//gán nhãn lại cho các đỉnh.
for (int v = 1; v <= n; v++) {
if ((!chuaxet[v]) && (d[u] + Matrix[u][v] < d[v])) {
d[v] = d[u] + Matrix[u][v];
truoc[v] = u;
}
}
}
}
}
void main(void) {
Init();
Dijkstra();
Result();
getch();
}Input:
9
1 9
0 6 5 0 8 0 0 0 0
6 0 4 0 0 7 0 0 0
5 4 0 4 0 0 0 0 0
0 0 4 0 4 0 6 0 0
8 0 0 4 0 0 0 6 0
0 7 0 0 0 0 5 0 6
0 0 0 6 0 5 0 4 3
0 0 0 0 6 0 4 0 5
0 0 0 0 0 6 3 5 0
dinh nghia.
1 tuong ung voi dinh A
2 tuong ung voi dinh B
3 tuong ung voi dinh C
4 tuong ung voi dinh D
5 tuong ung voi dinh E
6 tuong ung voi dinh F
7 tuong ung voi dinh G
8 tuong ung voi dinh H
9 tuong ung voi dinh IOutput:
So dinh: 9
Duong di ngan nhat tu A den I la
I<=G<=D<=C<=A
Do dai duong di la: 18