Tìm kiếm
Latest topics
Thuật toán Dijkstra
bkiz :: Giáo Trình :: Toán Rời Rạc
Trang 1 trong tổng số 1 trang
Thuật toán Dijkstra
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;
}
}
}
}
/*Đầ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;
}
}
}
}
Similar topics
» Thuật toán Floy
» THUẬT TOÁN KRUSKAL
» THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DFS)
» Thuật toán DDA (Digital Differential Analizer)
» THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (Breadth First Search)
» THUẬT TOÁN KRUSKAL
» THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DFS)
» Thuật toán DDA (Digital Differential Analizer)
» THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (Breadth First Search)
bkiz :: Giáo Trình :: Toán Rời Rạc
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
|
|
Mon Jun 24, 2013 11:27 pm by hangme
» host facebook
Mon Apr 02, 2012 2:26 pm by Admin
» Cyberlink PowerDirector 9 key full
Thu Mar 29, 2012 5:00 pm by Admin
» PowerDirector 10 Ultra
Fri Mar 23, 2012 6:15 pm by Admin
» Mảng - Nhập mảng số nguyên, tính tổng phần tử dương, tìm số hoàn hảo, tìm max, min, sắp xếp từ lớn đến nhỏ, từ nhỏ đến lớn
Sun Mar 18, 2012 9:17 pm by Admin
» HTML+CSS Form đăng nhập
Tue Sep 13, 2011 10:38 pm by Admin
» HTML+javascript : Lịch Dương
Thu Sep 08, 2011 5:15 pm by Admin
» HTML+javascript : Đòng hồ điện tử
Thu Sep 08, 2011 5:06 pm by Admin
» HTML: Form Đăng nhập
Thu Sep 08, 2011 4:42 pm by Admin