題意

平面上有n個點(N<=100)，每個點的坐標均在-10000~10000之間。其中的一些點之間有連線。若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點直線的距離。現在的任務是找出從一點到另一點之間的最短路徑。

分析

先算出點與點之間的距離

距離=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))

然后就很好做了

var
n,i,j,k,s,t,m,x1,y1:longint;
x,y:array[0..200]of longint;
a:array[0..200,0..200]of real;
begin
? ? readln(n);
? ? for i:=1 to n do
? ? readln(x[i],y[i]);
? ? readln(m);
? ? fillchar(a,sizeof(a),127);
? ? for i:=1 to m do
? ? begin
? ? ? ? readln(x1,y1);
? ? ? ? a[x1,y1]:=sqrt(sqr(x[x1]-x[y1])+sqr(y[x1]-y[y1]));
? ? ? ? a[y1,x1]:=a[x1,y1];
? ? end;
? ? read(s,t);
? ? for i:=1 to n do
? ? for j:=1 to n do
? ? for k:=1 to n do
? ? if a[j,i]+a[k,i]<a[j,k] then a[j,k]:=a[j,i]+a[k,i];
? ? write(a[s,t]:0:2);
end.

轉載于:https://www.cnblogs.com/YYC-0304/p/9500146.html

總結

以上是生活随笔為你收集整理的最短路径问题(Floyd算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。