zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Thuật toán BELLMAN-FORD

Chia sẻ: Pham Linh Dan | Ngày: | Loại File: PDF | Số trang:5

Báo xấu

737
lượt xem 91
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thuật toán BELLMAN-FORD là một thuật tóan tính các đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng có trọng số(trong đó một số cung có thể có trọng tâm). Thuật toán Dijkstra giải cùng bài toán này với thời gian chạy thấp hơn nhưng đòi hỏi trọng số của các cung phải có giá trị âm.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán BELLMAN-FORD

THU T TOÁN BELLMAN-FORD
Thu vien Hoc Lieu Mo Viet Nam module: m48086 1 Thu t toán Bellman-Ford∗ Lê Văn Tám This work is produced by Thu vien Hoc Lieu Mo Viet Nam and licensed under the Creative Commons Attribution License † Tóm t t n i dung Thu t toán Bellman-Ford Thu t toán Bellman-Ford là m t thu t toán tính các đư ng đi ng n nh t ngu n đơn trong m t đ th có hư ng có tr ng s (trong đó m t s cung có th có tr ng s âm). Thu t toán Dijkstra gi i cùng bài toán này v i th i gian ch y th p hơn, nhưng l i đòi h i tr ng s c a các cung ph i có giá tr không âm. Do đó, thu t toán Bellman-Ford thư ng ch đư c dùng khi có các cung v i tr ng s âm. Thu t toán Bellman Ford ch y trong th i gian O(V·E), trong đó V là s đ nh và E là s cung c a đ th . 1 N i dung thu t toán function BellmanFord(danh_sách_đ nh, danh_sách_cung, ngu n) // hàm yêu c u đ th đưa vào dư i d ng m t danh sách đ nh, m t danh sách cung // hàm tính các giá tr kho ng_cách và đ nh_li n_trư c c a các đ nh, // sao cho các giá tr đ nh_li n_trư c s lưu l i các đư ng đi ng n nh t. // bư c 1: kh i t o đ th for each v in danh_sách_đ nh: if v is ngu n then kho ng_cách(v) := 0 else kho ng_cách(v) := vô cùng đ nh_li n_trư c(v) := null // bư c 2: k t n p c nh for i from 1 to size(danh_sách_đ nh): for each (u,v) in danh_sách_cung: if kho ng_cách(v) > kho ng_cách(u) + tr ng_s (u,v) : kho ng_cách(v) := kho ng_cách(u) + tr ng_s (u,v) đ nh_li n_trư c(v) := u // bư c 3: ki m tra chu trình âm for each (u,v) in danh_sách_cung: if kho ng_cách(v) > kho ng_cách(u) + tr ng_s (u,v) : error "Đ th ch a chu trình âm" ∗ Version 1.1: Jan 19, 2011 2:37 pm GMT+7 † http://creativecommons.org/licenses/by/3.0/ http://voer.vn/content/m48086/1.1/
Thu vien Hoc Lieu Mo Viet Nam module: m48086 2 2 Ch ng minh tính đúng đ n Tính đúng đ n c a thu t toán có th đư c ch ng minh b ng quy n p. Thu t toán có th đư c phát bi u chính xác theo ki u quy n p như sau: B đ . Sau i l n l p vòng for: 1. N u Kho ng_cách(u) không có giá tr vô cùng l n, thì nó b ng đ dài c a m t đư ng đi nào đó t s t i u; 2. N u có m t đư ng đi t s t i u qua nhi u nh t i cung, thì Kho ng_cách(u) có giá tr không vư t quá đ dài c a đư ng đi ng n nh t t s t i u qua t i đa i cung. Ch ng minh. Trư ng h p cơ b n: Xét i=0 và th i đi m trư c khi vòng for đư c ch y l n đ u tiên. Khi đó, v i đ nh ngu n kho ng_cách(ngu n) = 0, đi u này đúng. Đ i v i các đ nh u khác, kho ng_cách(u) = vô cùng, đi u này cũng đúng vì không có đư ng đi nào t ngu n đ n u qua 0 cung. Trư ng h p quy n p: Ch ng minh câu 1. Xét th i đi m khi kho ng cách t i m t đ nh đư c c p nh t b i công th c kho ng_cách(v) := kho ng_cách(u) + tr ng_s (u,v). Theo gi thi t quy n p, kho ng_cách(u) là đ dài c a m t đư ng đi nào đó t ngu n t i u. Do đó, kho ng_cách(u) + tr ng_s (u,v) là đ dài c a đư ng đi t ngu n t i u r i t i v. Ch ng minh câu 2: Xét đư ng đi ng n nh t t ngu n t i u qua t i đa i cung. Gi s v là đ nh li n ngay trư c u trên đư ng đi này. Khi đó, ph n đư ng đi t ngu n t i v là đư ng đi ng n nh t t ngu n t i v qua t i đa i-1 cung. Theo gi thuy t quy n p, kho ng_cách(v) sau i-1 vòng l p không vư t quá đ dài đư ng đi này. Do đó, tr ng_s (v,u) + kho ng_cách(v) có giá tr không vư t quá đ dài c a đư ng đi t s t i u. Trong l n l p th i, kho ng_cách(u) đư c l y giá tr nh nh t c a kho ng_cách(v) + tr ng_s (v,u) v i m i v có th . Do đó, sau i l n l p, kho ng_cách(u) có giá tr không vư t quá đ dài đư ng đi ng n nh t t ngu n t i u qua t i đa i cung. Khi i b ng s đ nh c a đ th , m i đư ng đi tìm đư c s là đư ng đi ng n nh t toàn c c, tr khi đ th có chu trình âm. N u t n t i chu trình âm mà t đ nh ngu n có th đi đ n đư c thì s không t n t i đư ng đi nh nh t (vì m i l n đi quanh chu trình âm là m t l n gi m tr ng s c a đư ng). 3 ng d ng trong đ nh tuy n M t bi n th phân tán c a thu t toán Bellman-Ford đư c dùng trong các giao th c đ nh tuy n vector kho ng cách, ch ng h n giao th c RIP (Routing Information Protocol). Đây là bi n th phân tán vì nó liên quan đ n các nút m ng (các thi t b đ nh tuy n) trong m t h th ng t ch (autonomous system), ví d m t t p các m ng IP thu c s h u c a m t nhà cung c p d ch v Internet (ISP). Thu t toán g m các bư c sau: 1. M i nút tính kho ng cách gi a nó và t t c các nút khác trong h th ng t ch và lưu tr thông tin này trong m t b ng. 2. M i nút g i b ng thông tin c a mình cho t t c các nút lân c n. 3. Khi m t nút nh n đư c các b ng thông tin t các nút lân c n, nó tính các tuy n đư ng ng n nh t t i t t c các nút khác và c p nh t b ng thông tin c a chính mình. Như c đi m chính c a thu t toán Bellman-Ford trong c u hình này là • Không nhân r ng t t • Các thay đ i c a tô-pô m ng không đư c ghi nh n nhanh do các c p nh t đư c lan truy n theo t ng nút m t. • Đ m d n đ n vô cùng (n u liên k t h ng ho c nút m ng h ng làm cho m t nút b tách kh i m t t p các nút khác, các nút này v n s ti p t c ư c tính kho ng cách t i nút đó và tăng d n giá tr tính đư c, trong khi đó còn có th x y ra vi c đ nh tuy n thành vòng tròn) http://voer.vn/content/m48086/1.1/
Thu vien Hoc Lieu Mo Viet Nam module: m48086 3 4 Cài đ t C #include #include /* Let INFINITY be an integer value not likely to be confused with a real weight, even a negative one. */ #define INFINITY ((1 14)-1) typedef struct { int source; int dest; int weight; } Edge; void BellmanFord(Edge edges[], int edgecount, int nodecount, int source) { int *distance = malloc(nodecount * sizeof *distance); int i, j; for (i=0; i < nodecount; ++i) distance[i] = INFINITY; distance[source] = 0; for (i=0; i < nodecount; ++i) { for (j=0; j < edgecount; ++j) { if (distance[edges[j].source] != INFINITY) { int new_distance = distance[edges[j].source] + edges[j].weight; if (new_distance < distance[edges[j].dest]) distance[edges[j].dest] = new_distance; } } } for (i=0; i < edgecount; ++i) { if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) { puts("Negative edge weight cycles detected!"); free(distance); return; } } for (i=0; i < nodecount; ++i) { printf("The shortest distance between nodes %d and %d is %d\n", source, i, distance[i]); } free(distance); return; } int main(void) http://voer.vn/content/m48086/1.1/
Thu vien Hoc Lieu Mo Viet Nam module: m48086 4 { /* This test case should produce the distances 2, 4, 7, -2, and 0. */ Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2}, {2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2}, {4,0, 6}, {4,2, 7}}; BellmanFord(edges, 10, 5, 4); return 0; } http://voer.vn/content/m48086/1.1/

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.