Nguồn đề bài: http://vn.spoj.com/problems/FLOYD/
1. Đề bài FLOYD Dijkstra căn bản
Cho đơn đồ thị vô hướng N đỉnh và M cạnh, trọng số các cạnh đều nguyên dương. Có 2 loại câu hỏi :
0 u v : Cho biết đường đi ngắn nhất từ u tới v có độ dài là bao nhiêu.
1 u v : Hãy chỉ ra 1 đường đi ngắn nhất từ u => v
Bài cơ bản này nhằm kiểm tra kỹ năng xây dựng các module chương trình con dành cho truy vết 1 cách hợp lý, sử dụng nhuần nhuyễn chương trình con, lời gọi hàm .
Input
Dòng 1 : 3 số nguyên N , M , K . ( 1 ≤ N ≤ 100 , 1 ≤ M ≤ N*(N-1)/2 , 1 ≤ K ≤ 1000 )
M dòng tiếp theo , dòng thứ i gồm 3 số nguyên dương u , v , c cho biết cạnh (u,v) có trọng số là c ( 1 ≤ c ≤ 10000 )
K dòng tiếp theo là K câu hỏi , dòng thứ j sẽ có định dạng như đã nêu ở trên .
Output
Ứng với mỗi câu hỏi trong K câu hỏi thì ta phải trả lời trên mỗi dòng như sau .
Câu hỏi 0 u v : Ghi ra 1 số nguyên duy nhất là độ dài đường đi ngắn nhất từ u -> v.
Câu hỏi 1 u v : Ghi ra số đầu tiên là số X là số đỉnh trên đường đi ngắn nhất này , tiếp đó ghi ra X số là chỉ số các đỉnh theo thứ tự xuất hiện trên hành trình .
Example
Input:
3 3 2
1 2 3
2 3 1
1 3 5
0 1 2
1 1 3
Output:
3
3 1 2 3
2. code tham khảo Dijkstra, Floyd (pascal và c++)
a. Code Dijkstra Pascal
const fi='';
nmax=100;
vc=100000;//high(longint);
type data=longint;
var
f:text;
n,m,k:data;
A:array[0..nmax+1,0..nmax+1] of data;
D:array[0..nmax+1] of data;
free:array[0..nmax+1] of boolean;
trace:array[0..nmax+1] of data;
luu:array[0..nmax+1] of data;
spt:data;
procedure dijkstra(s,t:data);
var i,j,u,v,min:data;
begin
for i:=1 to n do
begin
free[i]:=true;
d[i]:=a[s,i];
trace[i]:=s;
end;
repeat
min:=vc; u:=0;
for i:=1 to n do
if (free[i]) and (d[i]<min) then
begin
min:=d[i];
u:=i;
end;
if (u=0) or (u=t) then break;
free[u]:=false;
for v:=1 to n do
begin
if (free[v]) and (d[v]>d[u]+a[u,v]) then
begin
d[v]:=d[u]+a[u,v];
trace[v]:=u;
end;
end;
until FALSE;
end;
procedure truyvet(v:data);
var x:data;
i:data;
begin
if trace[v]<>0 then
begin
truyvet(trace[v]);
inc(spt);
luu[spt]:=v;
end
else
begin
inc(spt);
luu[spt]:=v;
end;
end;
procedure docfile;
var i,j,u,v,c,tl:data;
begin
assign(f,fi); reset(f);
readln(f,n,m,k);
for i:=1 to n do
for j:=1 to n do
if i=j then
a[i,j]:=0
else
a[i,j]:=vc;
for i:=1 to m do
begin
readln(f,u,v,c);
a[u,v]:=c;
a[v,u]:=c;
end;
for i:=1 to k do
begin
readln(f,tl,u,v);
if tl=0 then
begin
dijkstra(u,v);
writeln(d[v]);
end
else
begin
dijkstra(u,v);
if u<>v then
begin
spt:=0;
trace[u]:=0;
truyvet(v);
write(spt,' ');
for j:=1 to spt do
write(luu[j],' ');
writeln;
end
else
writeln('2 ',u,' ',v);
end;
end;
close(f);
end;
begin
docfile;
readln;
end.b. Code Dijkstra c++
#include <bits/stdc++.h>
using namespace std;
const int maxn=100;
const int maxd=10e6;
int n,m,k;
int a[maxn][maxn];
void Init()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
a[i][j]=maxd;
int u,v,c;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&c);
a[u][v]=c;
a[v][u]=c;
}
}
void Solve()
{
while(k--)
{
int t,u, v;
scanf("%d%d%d",&t,&u,&v);
vector<int> L(n+2,0);
vector<int> Prev(n+2,0);
vector<int> Visit(n+2,0);
for (int i=1;i<=n;i++) L[i]=maxd;
L[u]=0;
while(1)
{
int u=0;
int min1=maxd;
for (int i=1;i<=n;i++)
{
if(!Visit[i] && L[i]<min1)
{
min1=L[i];
u=i;
}
}
if(u==0 || u==v) break;
Visit[u]=1;
for (int i=1;i<=n;i++)
{
if(!Visit[i] && L[i]>L[u]+a[u][i])
{
L[i]=L[u]+a[u][i];
Prev[i]=u;
}
}
}
if(t==0)
{
printf("%dn",L[v]);
}
else
{
stack<int> st;
while(v != u)
{
st.push(v);
v=Prev[v];
}
printf("%d %d ",st.size()+1,u);
while(!st.empty())
{
printf("%d ",st.top());
st.pop();
}
printf("n");
}
}
}
int main()
{
Init();
Solve();
}c. Code Floyd Pascal
const INP = '' ;
OUT = '' ;
maxn = 100 ;
maxc = 10000000 ;
var n , m , cau_hoi : integer ;
a : array[1..maxn,1..maxn] of longint ;
trace : array[1..maxn,1..maxn] of byte ;
fi , fo : text ;
procedure answer ;
var
i , j , u , v , pt , loai : integer ;
l : array[1..maxn] of integer ;
procedure truy_vet( u , v : integer ) ;
var
k : integer ;
begin
k := trace[u,v] ;
if k = 0 then begin
inc( pt ) ;
l[pt] := v ;
exit ;
end ;
truy_vet( u , k ) ;
truy_vet( k , v ) ;
end ;
begin
for i := 1 to cau_hoi do begin
read( fi , loai , u , v ) ;
if loai = 0 then writeln( fo , a[u,v] ) { cau hoi loai 0 }
else
{ cau hoi loai 1 }
if a[u,v] < 0 then writeln( fo , -1 )
else begin
pt := 1 ;
l[1] := u ;
truy_vet( u , v ) ;
write( fo , pt ) ;
for j := 1 to pt do write( fo , ' ', l[j] ) ;
writeln( fo ) ;
end ;
end ;
end ;
procedure process ;
var
k , u, v : longint ;
begin
for k := 1 to n do { Floyd }
for u := 1 to n do
for v := u + 1 to n do
if a[u,v] > a[u,k] + a[k,v] then begin
a[u,v] := a[u,k] + a[k,v] ;
a[v,u] := a[u,v] ;
trace[u,v] := k ;
trace[v,u] := k ;
end ;
for u := 1 to n do
for v := 1 to n do
if a[u,v] = maxc then a[u,v] := -1 ; { Khong ton tai duong di }
end ;
procedure nhapdl ;
var
i , j, u , v , val : longint ;
begin
read( fi , n , m , cau_hoi ) ;
for i := 1 to n do
for j := 1 to n do a[i,j] := maxc ;
for i := 1 to m do begin
read( fi , u , v , val ) ;
a[u,v] := val ;
a[v,u] := val ;
end ;
for i := 1 to n do a[i,i] := 0 ;
end ;
procedure mofile ;
begin
assign( fi , INP ) ; reset( fi ) ;
assign( fo , OUT ) ; rewrite( fo ) ;
end ;
procedure dongfile ;
begin
close( fi ) ; close( fo ) ;
end ;
BEGIN
mofile ;
nhapdl ;
process ;
answer ;
dongfile ;
END.
Thuật toán tìm đường đi ngắn nhất, thuat toan floyd, dijkstra c++ pascal toan roi rac, floyd’s algorithm, dijkstra algorithm
