[Q] duong di ngan nhat! help me!

[sboy_ht]

Bạn nào biết rõ về thuật toán tìm đường đi ngắn nhất trong đồ thị không? Bữa trước, mình có xem qua về một thuật toán nói về vấn đề này (hình nhu dis-tra (phát âm gần như vậy) thì phải), nhưng mình không hiểu lắm. Bạn nào giúp mình nhé!
Tiện thể làm cho mình bài này luôn, được không?

Đề: cho n thành phố, được đánh số từ 1..n; và r con đường đi qua các thành phố đó. Hãy tìm con đường ngắn nhất đi từ thành phố 1 đến thành phố n.

INPUT gồm:
- Dòng 1: số thành phố (n<=100)
- Dòng 2: số con đưởng (r<=10000) thì phải, không nhớ rõ lắm nhưng cũng gần như vậy đấy
- r dòng tiếp theo gồm các số
d:thành phố đầu
c:thành phố cuối
l:độ dài đoạn đường nối từ thành phố d tới c
OUTPUT gồm: độ dài đoạn đường ngắn nhất từ 1->n

[del_gate]

thuat toan dijstra rat de
Ve co ban nhu sau

for i := 1 to n do tr[i] := i;
for k := 1 to n do
for i := 1 to n do
for j := 1 to n do
if a[i,j] > a[i,k] + a[k,j] then
begin
a[i,j] := a[i,k] + a[k,j];
tr[j] := k;
end;

Ve co ban chi co vay. Hen dip khac mionh se noi ro hon.
Co gi thi cu mail cho minh the_limit17@yahoo.com

[del_gate]

Neu ban muon tim hieu sau ve do thi thi cu mua cuon 'Li thuyet do thi' ve ma coi. Trong do co nhieu thuat toan ve do thi lam.

[hiensmart]

Hình như U lộn wa floyd rùi

[hmt]

to: del_gate:đây không phải là dijktra mà là floyd .

[hiensmart]

Những người đc cho cũng như ko đc cho bài này đâu rùi lên bàn luận đi chứ, sao cứ chú trọng dzô tình tiết nhỏ nhặt ko dzậy, tiện thể trả lời luôn bài bên "Đuờng đi ngắn nhất" lun nha

[real_time]

hihi các bạn cãi nhau làm gì vì cả dijktra và floyd đều là thuật toán tìm đường đi ngắn nhất dùng cách nào cũng có mặt lợi mặt hại của nó cả!

[hiensmart]

Rốt cục là các bác đang nó dzề cái gì vậy, quay lại chủ đề chính đi chứ

[skywalker]

Dijkstra là thuật toán tìm đường đi ngắn nhất từ 1 đỉnh đến 1 tất cả các đỉnh khác, còn Floyd là tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh,
program dijkstra;
const fi='dijkstra.inp';
fo='dijkstra.out';
con=50;
var f1,f2:text;
i,j,k,n,new,l,r:integer;
a:array[1..100] of integer;
m:array[1..100,1..100] of integer;
dau,luu:array[1..100] of integer;
p:array[1..100] of boolean;
{----------------------------------------------------------------------------}
procedure nhap;
begin
assign(f1,fi);
reset(f1);
readln(f1,n,l,r);
for i:=1 to n do begin
read(f1,a[i]);
for j:=1 to a[i] do read(f1,k,m[i,k]);
readln(f1);
end;
close(f1);
fillchar(dau,sizeof(dau),con);
fillchar(p,sizeof(p),false);
end;
{----------------------------------------------------------------------------}
procedure tim_min;
var m,i:integer;
begin
m:=con;
for i:=1 to n do begin
if (dau[i]<m) and (p[i]=false) then begin
m:=dau[i];
k:=i;
end;
end;
end;
{----------------------------------------------------------------------------}
procedure tim;
begin
dau[l]:=0;
k:=l;
repeat
p[k]:=true;
for i:=1 to n do begin
if (m[k,i]<>0) and (p[i]=false) then begin
new:=dau[k]+m[k,i];
if new<dau[i] then begin
dau[i]:=new;
luu[i]:=k;
end;
end;
end;
tim_min;
until p[r]=true;
end;
{----------------------------------------------------------------------------}
procedure xuat;
var st,s:string;
begin
str(r,s);
st:=s;
assign(f2,fo);
rewrite(f2);
i:=r;
repeat
i:=luu[i];
str(i,s);
st:=s+' '+st;
until i=l;
write(f2,st);
close(f2)
end;
{----------------------------------------------------------------------------}
begin
nhap;
tim;
xuat;
end.

[skywalker]

mấy bác tải cái này về coi cho dễ đọc