Thuật toán tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại được Dijkstra đề nghị áp dụng cho trường hợp đồ thị có hướng với trọng số không âm. Sau đây hãy cùng TTnguyen tìm hiểu lý thuyết và một số bài tập thuật toán dijkstra nhé.
Xem thêm:
I. Thuật toán Dijkstra (dijkstra algorithm)
Thuật toán được thực hiện trên cơ sở gán tạm thời cho các đỉnh. Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất tới đỉnh đó. Các nhãn này sẽ được biến đổi (tính lại) nhờ một thủ tục lặp, mà ở mỗi bước lặp một số đỉnh sẽ có nhãn không thay đổi, nhãn đó chính là độ dài đường đi ngắn nhất từ s đến đỉnh đó.
II. Bài tập thuật toán dijkstra
Tìm đường đi ngắn nhất từ đỉnh x1 đến các đỉnh còn lại của đồ thị vô hướng:
Lời giải
Từ bảng trên ta có đường đi ngắn nhất từ x1 đến các đỉnh là: X1X5X2 (độ dài 8); X1X4 (9); X1X5X2X3 (13); X1X5 (6); X1X5X6 (13); X1X5X2X7 (14); X1X5X2X3X8 (16); X1X5X10X9 (11); X1X5X10 (10); X1X5X10X11 (17)
Các đường đi được minh họa trên đồ thị sau:
Tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị có hướng:
Từ bảng trên, ta có đường đi ngắn nhất từ A đến các đỉnh là: AHEB (6); AHIFC (9); AHIFKGD (16); AHE (3) AFHIF (7); AHIFCKG (14); AH (1); AHI (3); AHIFCK (11); AHIFCKM (16).
a. Tìm đường đi ngắn nhất từ x1 đến x14
Từ bảng trên ta có đường đi ngắn nhất từ x1 đến x14 là: X1X6X5X8X10X13X14 hoặc X1X6X5X8X10X11X14 và độ dài là: 25.
b. Tìm đường đi ngắn nhất từ x1 đến x14 có chứa X8X9
Từ bảng trên ta có đường đi ngắn nhất từ x1 đến x14 có chứa X8X9 là:x1x6x5x9x8x10x11x14 , hoặc x1x6x5x9x8x10x13x14 , hoặc x1x6x9x8x10x11x14 , hoặc x1x6x9x8x10x13x14 với chiều dài là: 31
c. Tìm đường đi ngắn nhất từ x1 đến x14 có chứa đỉnh X7
Vậy đường đi ngắn nhất từ x1 đến x14 có chứa đỉnh X7 là: X1 X6 X5 X8 X7 X11 X14, và độ dài đường đi bằng: 27
III. Giải thuật dijkstra
1. Mô tả thuật toán
Các bước chính của thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trên đồ thị G=(V,E,W) được mô tả như sau:
Bước 1 : T=V; Da = 0; Di = ∞, Vi ≠ a.
Bước 2 : Lặp cho đến khi z ∉T:
– Lấy ra khỏi T đỉnh Vi có Di nhỏ nhất
– Đánh nhãn lại cho mọi Vj kề Vi và Vj T ∈ theo công thức: Dj = min{Dj, Di+Wij}
Thuật toán có thể được mô tả bằng thủ tực Dijkstra như sau:
void Dijkstra(void)
/*Đầu vào G=(V, E) với n đỉnh có ma trận trọng số A[u,v]≥ 0; s∈V */
/*Đầu ra là khoảng cách nhỏ nhất từ s đến các đỉnh còn lại d[v]: v∈V*/
/*Truoc[v] ghi lại đỉnh trước v trong đường đi ngắn nhất từ s đến v*/
{
/* Bước 1: Khởi tạo nhãn tạm thời cho các đỉnh*/
for (v∈ V) {
d[v] = A[s, v];
truoc[v] = s;
}
d[s] = 0;
T = V\ {
s
}; /*T là tập đỉnh có nhãn tạm thời*/
/* Bước lặp */
while (T != φ) {
Tìm đỉnh u∈ T sao cho d[u] = min {
d[z] | z∈ T
};
T = T\ {
u
}; /*cố định nhãn đỉnh u*/ ;
For(v∈ T) {
/* Gán lại nhãn cho các đỉnh trong T*/
If(d[v] > d[u] + A[u, v]) {
d[v] = d[u] + A[u, v];
truoc[v] = u;
}
}
}
}
2. Code thuật toán dijkstra
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <dos.h>
#define MAX 50
#define TRUE 1
#define FALSE 0
int n, s, t;
char chon;
int truoc[MAX], d[MAX], CP[MAX][MAX];
int final[MAX];
void Init(void) {
FILE * fp;
int i, j;
fp = fopen(“ijk1.in”, ”r”);
fscanf(fp, ” % d”, & n);
printf(“\n So dinh: % d”, n);
printf(“\n Ma tran khoang cach: ”);
for (i = 1; i <= n; i++) {
printf(“\n”);
for (j = 1; j <= n; j++) {
fscanf(fp, “ % d”, & CP[i][j]);
printf(“ % 3 d”, CP[i][j]);
if (CP[i][j] == 0) CP[i][j] = 32000;
}
}
fclose(fp);
}
void Result(void) {
int i, j;
printf(“\n Duong di ngan nhat tu % d den % d la\ n”, s, t);
printf(“ % d <= ”, t);
i = truoc[t];
while (i != s) {
printf(“ % d <= ”, i);
i = truoc[i];
}
printf(“ % d”, s);
printf(“\n Do dai duong di la: % d”, d[t]);
getch();
}
void Dijkstra(void) {
int v, u, minp;
printf(“\n Tim duong di tu s = ”);
scanf(“ % d”, & s);
printf(“den“);
scanf(“ % d”, & t);
for (v = 1; v <= n; v++) {
d[v] = CP[s][v];
truoc[v] = s;
final[v] = FALSE;
}
truoc[s] = 0;
d[s] = 0;
final[s] = TRUE;
while (!final[t]) {
minp = 2000;
for (v = 1; v <= n; v++) {
if ((!final[v]) && (minp > d[v])) {
u = v;
minp = d[v];
}
}
final[u] = TRUE; // u- la dinh co nhan tam thoi nho nhat
if (!final[t]) {
for (v = 1; v <= n; v++) {
if ((!final[v]) && (d[u] + CP[u][v] < d[v])) {
d[v] = d[u] + CP[u][v];
truoc[v] = u;
}
}
}
}
}
void main(void) {
clrscr();
Init();
Dijkstra();
Result();
getch();
}
Trên đây là bài tập thuật toán dijkstra toán rời rạc và cách cách đặt thuật toán trên ngôn ngữ lập trình C++. Cảm ơn các bạn đã theo dõi trên ttnguyen.net.
