CHỦ ĐỀ NIÊN LUẬN SỐ 10 - CÔ TÚ

+ Đối với chủ đề này các bạn sử dụng thuật toán Floyd thay cho Dijkstra vì Floyd là do cho bất kỳ cặp đỉnh nào và đồ thị là có hướng còn Dijkstra thì đồ thì vô hướng .
+ Mình không thể show source code ra đây được các bạn tự làm lấy nhé , mình chỉ chia sẻ thuật toán để các bạn tham khảo làm thôi. Ngoài ra ai còn thuật toán nào hay thì up lên đây chia sẻ cùng anh em nhé . Ngoài cách này các bạn có thể tham khảo thêm tài liệu của thầy Thắng trong quyển Toán rời rạc II chương các bài toán tối ưu về đồ thị có đề cập đến vấn đề này .
+ Mọi thắc mắc anh em cứ show soure code lên đây cùng bình luận tham khảo và chỉnh sữa.
+ Còn về tải liệu tham khảo mình up này bạn cứ để là Tham khảo trên forum K4info.forumr.net vì trang forum mình là 1 website bình thường. Mình phải tự tin về forum lớp mình chứ. Forum mình là 1 forum học tập mà .



Sau đây là thuật toán và giải thuật:




Thuật toán (Floyd):

Dữ liệu: Ma trận trọng số C của đồ thị.
Kết quả: Ma trận D cho biết khoảng cách của tất cả các cặp đỉnh.

Code:




1  BEGIN
2    for  i  := 1  to  n  do                   
3        for  j  :=  1  to  n  do 
4    begin  D[i,j]  :=  C[i,j]  ; TRUOC[i,j]  :=  0  end ;
5    for  k  :=  1  to  n  do                   
6  for  i  :=  1  to  n  do                   
7    for  j  :=  1  to  n  do 
8    if  D[i,k] + D[k,j]  <  D[i,j]  then
9        begin   
10                            D[i,j]  :=  D[i,k] + D[k,j]  ; 
11  TRUOC[i,j]  :=  k
12        end ;
13  END .
Nếu  TRUOC[i,j] = 0  thì đưòng đi ngắn nhất từ đỉnh  i  đến đỉnh  j  chính là
cạnh  (i, j). 
Để in ra các đỉnh trung gian trên đường đi ngắn nhất từ đỉnh  i  đến đỉnh  j  ta
dùng thủ tục đệ quy sau đây:
 
1  procedure Duong_di( i, j ) ;
2  begin
3  k  :=  TRUOC[i,j]  ;
4 if  k = 0  then  Exit ;
5 Duong_di( i, k ) ;
6 write( k ) ;
7  Duong_di( k, j ) ;
8  end ;





Mới thi xong là làm tới niên luận hả bác.
Nghỉ ngơi chút đi. Học nhiều quá coi chừng tẩu hoả nhập ma

Tâm à bữa đó Tâm không đi nên không nghe cô Tú hướng dẫn, bài của mình là sử dụng thuật toán Dijkstra có hướng đó. k có floyd đâu.hihi Ham ngủ

ông hỏi lại cô chưa z ??? cô có cho làm thuật toán Ford hok ?????

haizzzzz mệt ghê vậy đó. cô nói rõ ràng. tui cũng thấy la đây nè