Tìm đường đi ngắn nhất Dijkstra cài đặt bằng C/C++

Tìm đường đi ngắn nhất Dijkstra cài đặt bằng C/C++

Xét đồ thị G =<V, E>: trong đó |V| = n, |E| = m. Với mỗi cạnh (u, v)∈E, ta đặt tương ứng với nó một số thực A<u,v> được gọi là trọng số của cạnh. Ta sẽ đặt A[u,v]=∞ nếu (u, v)∉E. Nếu dãy v0, v1,..., vk là một đường đi trên G thì tổng của tất cả các cạnh ( A[vi-1,vi]) được gọi là độ dài của đường đi.

Bài toán tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thể được phát biểu dưới dạng sau: Tìm đường đi ngắn nhất từ một đỉnh xuất phát s∈V(đỉnh nguồn) đến đỉnh cuối t∈V(đỉnh đích). Đường đi như vậy được gọi là đường đi ngắn nhất từ s đến t, độ dài của đường đi d(s,t) được gọi là khoảng cách ngắn nhất từ s đến (trong trường hợp tổng quát d(s,t) có thể âm). Nếu như không tồn tại đường đi từ s đến t thì độ dài đường đi d(s,t)=∞. Nếu như mỗi chu trình trong đồ thị đều có độ dài dương thì trong đường đi ngắn nhất sẽ không có đỉnh nào bị lặp lại, đường đi như vậy được gọi là đường đi cơ bản. Nếu như đồ thị tồn tại một chu trình nào đó có độ dài âm, thì đường đi ngắn nhất có thể không xác định, vì ta có thể đi qua chu trình âm đó một số lần đủ lớn để độ dài của nó nhỏ hơn bất kỳ một số thực cho trước nào.

1. Thuật toán gán nhãn.

Có rất nhiều thuật toán khác nhau được xây dựng để tìm đường đi ngắn nhất. Nhưng tư tưởng chung của các thuật toán đó có thể được mô tả như sau:

Từ ma trận trọng số A[u,v], u,v∈V, ta tìm cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v∈V. Mỗi khi phát hiện thấy d[u] + A[u,v] < d[v] thì cận trên d[v] sẽ được làm tốt lên bằng cách gán d[v] = d[u] + A[u, v]. Quá trình sẽ kết thúc khi nào ta không thể làm tốt hơn lên được bất kỳ cận trên nào, khi đó d[v] sẽ cho ta giá trị ngắn nhất từ đỉnh s đến đỉnh v. Giá trị d[v] được gọi là nhãn của đỉnh v. Ví dụ dưới đây thể hiện tư tưởng trên bằng một thuật toán gán nhãn tổng quát như sau:

 Ví dụ.Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh I trên đồ thị hình sau:

  • Bước 1.Gán cho nhãn đỉnh A là 0; 
  • Bước 2.Trong số các cạnh (cung) xuất phát từ A, ta chọn cạnh có độ dài nhỏ nhất, sau đó gán nhãn cho đỉnh đó bằng nhãn của đỉnh A cộng với độ dài cạnh tương ứng. Ta chọn được đỉnh C có trọng số AC = 5, nhãn d[C] = 0 + 5 = 5. 
  • Bước 3.Tiếp đó, trong số các cạnh (cung) đi từ một đỉnh có nhãn là A hoặc C tới một đỉnh chưa được gán nhãn, ta chọn cạnh sao cho nhãn của đỉnh cộng với trọng số cạnh tương ứng là nhỏ nhất gán cho nhãn của đỉnh cuối của cạnh. Như vậy, ta lần lượt gán được các nhãn như sau: d[B] = 6 vì d[B] <d[C] + | CB| = 5 + 4; d[E] = 8; Tiếp tục làm như vậy cho tới khi đỉnh I được gán nhãn đó chính là độ dài đường đi ngắn nhất từ A đến I. Thực chất, nhãn của mỗi đỉnh chính là đường đi ngắn nhất từ đỉnh nguồn tới nó. 

Quá trình có thể được mô tả như trong bảng dưới đây.

Bước Đỉnh được gán nhãn Nhãn các đỉnh Đỉnh đã dùng để gán nhãn
Khởi tạo A 0 A
1 C 0+5 =5 A
2 B 0+6 = 6 A
3 E 0+8 = 8 A
4 D 5+4 = 9 C
5 F 5+7 = 13 B
6 H 8+6 = 14 E
7 G 9+6 = 15 D
8 I 15 + 3 = 18 G

Như vậy, độ dài đường đi ngắn nhất từ A đến I là 18. Đường đi ngắn nhất từ A đến I qua các đỉnh: A-> C-> D -> G -> I.

2. Thuật toán Dijkstra.

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. 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 đó.

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;

   }

  }

 }

}

Chương trình cài đặt thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác của đồ thị có hướng với trọng số không âm được thực hiện như sau:

#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();

}

DIJKSTRA.IN input của bài toán

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 I

Output của chương trình.

So dinh: 9

Duong di ngan nhat tu A den I la

I<=G<=D<=C<=A

Do dai duong di la: 18

Bạn thấy bài viết này như thế nào?: 
Average: 6.6 (18 votes)
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Samsung cạnh tranh mạnh mẽ với Nokia về di động

Samsung cạnh tranh mạnh mẽ với Nokia về di động

Cơ quan nghiên cứu thị trường Strategy Analytics ngày 9/11 cho biết Samsung Electronics, nhà sản xuất điện thoại di động lớn thứ hai thế giới, đã trở thành hãng

Hướng dẫn tạo bộ cài đặt MacOS X 10.8 Mountain Lion trên USB

Hướng dẫn tạo bộ cài đặt MacOS X 10.8 Mountain Lion trên USB

Cuối cùng Apple cũng đã chính thức phát hành phiên bản MacOS X 10.8 Mountain Lion và người dùng có thể lên kho ứng dụng Mac AppStore để tải trực tiếp về để upgrade cho máy Mac của mình.

Thủ thuật xử lý DateTime trong MS SQL

Thủ thuật xử lý DateTime trong MS SQL

Hôm nay phải động đến vấn đề xử lý datetime trong SQL, lướt qua trên mạng thu thập về các hàm tiện ích phục vụ cho công việc.