Forum trường THPT Thái Phiên
Bạn hãy đăng nhập hoặc đăng kí làm thành viên của diễn đàn trường THPT Thái Phiên để góp vui với mọi người nhé !!
Forum trường THPT Thái Phiên
Bạn hãy đăng nhập hoặc đăng kí làm thành viên của diễn đàn trường THPT Thái Phiên để góp vui với mọi người nhé !!
Forum trường THPT Thái Phiên
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Forum trường THPT Thái Phiên

SMod thông báo: diễn đàn đóng cửa - Admin đi nghỉ mát rầu, Mem thích làm gì thì làm, chém thỏa mái
 
Trang ChínhTrang Chính  Latest imagesLatest images  Tìm kiếmTìm kiếm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  
Top posters
ngocsohn
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_lcapThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh I_voting_barThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_rcap 
admin
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_lcapThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh I_voting_barThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_rcap 
<rémyphú>
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_lcapThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh I_voting_barThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_rcap 
haihandsome94
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_lcapThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh I_voting_barThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_rcap 
muapro94
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_lcapThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh I_voting_barThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_rcap 
phucbyna8
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_lcapThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh I_voting_barThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_rcap 
badboy10a8
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_lcapThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh I_voting_barThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_rcap 
ngoc.huong182
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_lcapThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh I_voting_barThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_rcap 
nguyenlinh92
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_lcapThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh I_voting_barThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_rcap 
¶Ken
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_lcapThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh I_voting_barThuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Vote_rcap 
Latest topics
» Đón Giáng Sinh cùng StudyLink - Tháng 12/2015
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby studylink219 22/12/15, 09:48 am

» Học tiếng Anh với chương trình "Đôi bạn cùng tiến" tại StudyLink - Thá
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby studylink219 11/11/15, 02:37 pm

» Chương trình ưu đãi tháng 10/2015 - Trung tâm Anh ngữ StudyLink
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby studylink219 22/10/15, 03:46 pm

» Vui học tiếng Anh cùng Trung tâm Anh ngữ StudyLink - Tháng 9/2015
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby studylink219 25/09/15, 09:38 am

» Chương trình ưu đãi tháng 8/2015 - Trung tâm Anh ngữ StudyLink
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby studylink219 31/07/15, 03:47 pm

» Chương trình ưu đãi tháng 7/2015 tại Trung tâm Anh ngữ StudyLink
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby studylink219 15/07/15, 03:46 pm

» Chương trình ưu đãi tháng 6/2015 – Vui hè cùng StudyLink
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby studylink219 23/06/15, 02:29 pm

» Vui hè cùng StudyLink với chương trình Endless Summer tháng 5/2015
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby studylink219 07/05/15, 09:19 am

» Chương trình ưu đãi tháng 4/2015 tại Trung tâm Anh ngữ StudyLink
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby studylink219 13/04/15, 02:57 pm

» [Chia sẻ] Game casual "Bắn trứng khủng long" HOT 2014
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby dark_sky 13/11/14, 11:27 am

» [Chia sẻ] Game casual "Bắn trứng khủng long" HOT 2014
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby dark_sky 13/11/14, 11:27 am

» Khuyến mãi từ Trung tâm Anh ngữ StudyLink
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby studylink219 06/10/14, 04:40 pm

» Học cao đẳng có thể phải lấy bằng trung cấp?
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby miss123 05/01/14, 08:16 am

» Tuyển lập lờ, sinh viên chịu thiệt
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby miss123 05/01/14, 08:16 am

» Học cao đẳng có thể phải lấy bằng trung cấp?
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby motminh123 04/01/14, 09:03 pm

» Tuyển lập lờ, sinh viên chịu thiệt
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby motminh123 04/01/14, 09:02 pm

» Học cao đẳng có thể phải lấy bằng trung cấp?
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby ngocha123 04/01/14, 08:39 pm

» Tuyển lập lờ, sinh viên chịu thiệt
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby ngocha123 04/01/14, 08:39 pm

» Tặng 75% giá trị thẻ học tiếng anh, kỹ năng mềm, công nghệ thông tin
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby daihoctructuyen 23/07/13, 04:13 pm

» KiKi RPG – Phiêu lưu vào thế giới quỷ
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby phuongtep 08/06/13, 02:18 pm

» [UPDATE 2013] Topic tập hợp mỗi ngày 1 game chuẩn không cần chỉnh 100%
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Emptyby nguyenlinh92 06/06/13, 11:27 am

Most active topics
Những bài thơ tình hay nhất, ai yêu thơ thì xin mời
20-11 of 11A8
[Phần mềm cập nhật hằng ngày] Phần mềm hay
Cho em hỏi chút
Hot hot, chuyện lạ của lớp 11a8 nè
Tuyển dụng Moderator cho diễn đàn
Try Fu Production
Những câu chuyện tình yêu ý nghĩa
Vào chúc mừng sinh nhật của Vũ và Ngọc đi các bạn..........
[Tâm sự tình yêu] Ai là người bạn nghĩ đến đầu tiên...?

 

 Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh

Go down 
Tác giảThông điệp
ngocsohn
MOD
MOD
ngocsohn


Tổng số bài gửi Tổng số bài gửi : 434
Xu TP Xu TP : 21277052
Cảm ơn !! Cảm ơn !! : 11
Ngày sinh Ngày sinh : 21/12/1994
Tham gia ngày: Tham gia ngày: : 28/11/2010
Tuổi Tuổi : 29
Đến từ Đến từ : Đà Nẵng
Châm ngôn sống : sống có lý tưởng

Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Empty
Bài gửiTiêu đề: Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh   Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh Empty02/12/10, 08:20 am

Cho đơn đồ thị có hướng, có trọng số G=(V,E) với n đỉnh và m cạnh, Ma trận trọng số C[u,v]. Bài toán đặt ra là tính tất cả các d(u,v) là khoảng cách nhỏ nhất từ u đến v.

Ta sử dụng thuật toán FLOYD để giải quyết bài toán này. Từ ma trận trọng số ban đầu C, ta tính lại các C[u,v] thành đường đi ngắn nhất từ u đến v theo công thức:
C[u,v] := min (C[u,v], C[u,k] + C[k,v]) với mọi đỉnh k xét từ 1 đến n.

Tức là: Nếu đường đi đang có từ u đến v dài hơn đường đi từ u đến k cộng với đường đi từ k đến v thì ta ghi nhận lại đường đi ngắn nhất (hiện có) là đường đi qua k.

for k:=1 to n do
for u:=1 to n do
for v:=1 to n do
c[u,v] := min ( c[u,v] , c[u,k] + c[k,v] );

Chứng minh:
Gọi D[k,u,v] là độ dài đường đi ngắn nhất từ u đến v mà chỉ đi qua các đỉnh trung gian thuộc tập {1,2,…,k}. Rõ ràng ban đầu, khi k=0 thì D[0,u,v] =C[u,v] (đường đi trực tiếp).
Giả sử đã tính được các D[k-1,u,v], D[k,u,v] sẽ được tính bằng cách:

* Không đi qua đỉnh k, tức là chỉ sử dụng các đỉnh trung gian từ 1 đến k-1 thì
D[k,u,v] := D[k-1,u,v];
* Đi qua đỉnh k, khi đó đường đi ngắn nhất từ u đến v sẽ là nối của hai đường, một đường từ u đến k, một từ k đến v, và các đường con này chỉ đi qua các đỉnh trung gian từ 1..k-1
D[k,u,v] := min ( D[k-1,u,k] + D[k-1,k,v] )


Cài đặt :

Code:
program Shortest_Path_by_Floyd;
const
max = 100;
maxC = 10000;
var
c: array[1..max, 1..max] of Integer;
Trace: array[1..max, 1..max] of Integer;
n, S, F: Integer;

procedure LoadGraph;
var
i, m: Integer;
u, v: Integer;
begin
Readln(n, m, S, F);
for u := 1 to n do
for v := 1 to n do
if u = v then c[u, v] := 0 else c[u, v] := maxC;
for i := 1 to m do Readln(u, v, c[u, v]);
end;

procedure Floyd;
var
k, u, v: Integer;
begin
for u := 1 to n do
for v := 1 to n do Trace[u, v] := v;
for k := 1 to n do
for u := 1 to n do
for v := 1 to n do
if c[u, v] > c[u, k] + c[k, v] then
begin
c[u, v] := c[u, k] + c[k, v];
Trace[u, v] := Trace[u, k];
end;
end;

procedure PrintResult;
begin
if c[S, F] = maxC
then Writeln('Not found any path from ', S, ' to ', F)
else
begin
Writeln('Distance from ', S, ' to ', F, ': ', c[S, F]);
repeat
Write(S, '->');
S := Trace[S, F];
until S = F;
Writeln(F);
end;
end;

begin
Assign(Input, 'MINPATH.INP'); Reset(Input);
Assign(Output, 'MINPATH.OUT'); Rewrite(Output);
LoadGraph;
Floyd;
PrintResult;
Close(Input);
Close(Output);
end.
Về Đầu Trang Go down
http://thaiphiendn.org
 
Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» [Shock new] Mẹ Trương Thiều Hàm hành hạ bạn thân của cô ngay giữa đường phố
» Định Ngiã Giữa Pồ và Vợ ...................
» [Bói toán] Sự liên hệ giữa tên và số mệnh... ^-^
» Đại học không phải là con đường tiến thân duy nhất!
» Thuật toán kiểm tra xâu đối xứng

Permissions in this forum:Bạn không có quyền trả lời bài viết
Forum trường THPT Thái Phiên :: Góc học tập - Học trực tuyến :: -‘๑’-Chia sẻ kinh nghiệm học tập-‘๑’ :: -‘๑’- Phương pháp học tốt -‘๑’--
Chuyển đến 
Liên kết bạn bè: game iwin | game ky tien | game khu vuon dia dang | Xem phim