最短路徑Floyd算法-POJ1847Tram

定義　　Floyd算法又稱為弗洛伊德算法，插點法，是一種用于尋找給定的權重圖中頂點間最短路徑的算法。

核心思路

　　通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。

　　從圖的帶權鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；……；最後又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i号頂點到j号頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個後繼節點矩陣path來記錄兩點間的最短路徑。

　　采用的是松弛技術，對在i和j之間的所有其他點進行一次松弛。是以時間複雜度為O(n^3);

　　其狀态轉移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}

　　map[i,j]表示i到j的最短距離

　　K是窮舉i,j的斷點

　　map[n,n]初值應該為0，或者按照題目意思來做。

　　當然，如果這條路沒有通的話，還必須特殊處理,比如沒有map[i,k]這條路

算法過程

　　把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。

　　定義一個矩陣D用來記錄所插入點的資訊，D[i,j]表示從Vi到Vj需要經過的點，初始化D[i,j]=j。

　　把各個頂點插入圖中，比較插點後的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。

　　在G中包含有兩點之間最短道路的資訊，而在D中則包含了最短通路徑的資訊。

　　比如，要尋找從V5到V1的路徑。根據D，假如D(5,1)=3則說明從V5到V1經過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。

時間複雜度

　　O(n^3)

優缺點分析

　　Floyd算法适用于APSP(All Pairs Shortest Paths)，是一種動态規劃算法，稠密圖效果最佳，邊權可正可負。此算法簡單有效，由于三重循環結構緊湊，對于稠密圖，效率要高于執行|V|次Dijkstra算法。

　　優點：容易了解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單；

　　缺點：時間複雜度比較高，不适合計算大量資料。

算法實作

　　c語言：

　　#include<fstream>

　　#define Maxm 501

　　using namespace std;

　　ifstream fin("APSP.in");

　　ofstream fout("APSP.out");

　　int p,q,k,m;

　　int Vertex,Line[Maxm];

　　int Path[Maxm][Maxm],Map[Maxm][Maxm],Dist[Maxm][Maxm];

　　void Root(int p,int q)

　　{

　　if (Path[p][q]>0)

　　{

　　Root(p,Path[p][q]);

　　Root(Path[p][q],q);

　　}

　　else

　　{

　　Line[k]=q;

　　k++;

　　}

　　int main()

　　{

　　memset(Path,0,sizeof(Path));

　　memset(Map,0,sizeof(Map));

　　memset(Dist,0,sizeof(Dist));

　　fin >> Vertex;

　　for(p=1;p<=Vertex;p++)

　　for(q=1;q<=Vertex;q++)

　　{

　　fin >> Map[p][q];

　　Dist[p][q]=Map[p][q];

　　}

　　for(k=1;k<=Vertex;k++)

　　for(p=1;p<=Vertex;p++)

　　if (Dist[p][k]>0)

　　for(q=1;q<=Vertex;q++)

　　if (Dist[k][q]>0)

　　{

　　if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q))

　　{

　　Dist[p][q]=Dist[p][k]+Dist[k][q];

　　Path[p][q]=k;

　　}

　　for(p=1;p<=Vertex;p++)

　　{

　　for(q=p+1;q<=Vertex;q++)

　　{

　　fout << "/n==========================/n";

　　fout << "Source:" << p << '/n' << "Target " << q << '/n';

　　fout << "Distance:" << Dist[p][q] << '/n';

　　fout << "Path:" << p;

　　k=2;

　　Root(p,q);

　　for(m=2;m<=k-1;m++)

　　fout << "-->" << Line[m];

　　fout << '/n';

　　fout << "==========================/n";

　　}

　　fin.close();

　　fout.close();

　　return 0;

　　}

　　注解:無法連通的兩個點之間距離為0;

　　Sample Input

　　00 20 50 30 00 00 00

　　20 00 25 00 00 70 00

　　50 25 00 40 25 50 00

　　30 00 40 00 55 00 00

　　00 00 25 55 00 10 70

　　00 70 50 00 10 00 50

　　00 00 00 00 70 50 00

　　Sample Output

　　==========================

　　Source:1

　　Target 2

　　Distance:20

　　Path:1-->2

　　==========================

　　Source:1

　　Target 3

　　Distance:45

　　Path:1-->2-->3

　　==========================

　　Source:1

　　Target 4

　　Distance:30

　　Path:1-->4

　　==========================

　　Source:1

　　Target 5

　　Distance:70

　　Path:1-->2-->3-->5

　　==========================

　　Source:1

　　Target 6

　　Distance:80

　　Path:1-->2-->3-->5-->6

　　==========================

　　Source:1

　　Target 7

　　Distance:130

　　Path:1-->2-->3-->5-->6-->7

　　==========================

　　Source:2

　　Target 3

　　Distance:25

　　Path:2-->3

　　==========================

　　Source:2

　　Target 4

　　Distance:50

　　Path:2-->1-->4

　　==========================

　　Source:2

　　Target 5

　　Distance:50

　　Path:2-->3-->5

　　==========================

　　Source:2

　　Target 6

　　Distance:60

　　Path:2-->3-->5-->6

　　==========================

　　Source:2

　　Target 7

　　Distance:110

　　Path:2-->3-->5-->6-->7

　　==========================

　　Source:3

　　Target 4

　　Distance:40

　　Path:3-->4

　　==========================

　　Source:3

　　Target 5

　　Distance:25

　　Path:3-->5

　　==========================

　　Source:3

　　Target 6

　　Distance:35

　　Path:3-->5-->6

　　==========================

　　Source:3

　　Target 7

　　Distance:85

　　Path:3-->5-->6-->7

　　==========================

　　Source:4

　　Target 5

　　Distance:55

　　Path:4-->5

　　==========================

　　Source:4

　　Target 6

　　Distance:65

　　Path:4-->5-->6

　　==========================

　　Source:4

　　Target 7

　　Distance:115

　　Path:4-->5-->6-->7

　　==========================

　　Source:5

　　Target 6

　　Distance:10

　　Path:5-->6

　　==========================

　　Source:5

　　Target 7

　　Distance:60

　　Path:5-->6-->7

　　==========================

　　Source:6

　　Target 7

　　Distance:50

　　Path:6-->7

　　==========================

　　Matlab源代碼為

　　function [D,R]=floyd(a)

　　n=size(a,1);

　　D=a

　　for i=1:n

　　for j=1:n

　　R(i,j)=j;

　　end

　　for k=1:n

　　for i=1:n

　　for j=1:n

　　if D(i,k)+D(k,j)<D(i,j)

　　D(i,j)=D(i,k)+D(k,j);

　　R(i,j)=R(i,k);

　　end

　　在M檔案中建立

　　pascal語言：

　　program floyd;

　　var

　　st,en,f:integer;

　　n,i,j,x:integer;

　　a:array[1..10,1..10]of integer;

　　path,map1,map2:array[1..10,1..10]of integer;

　　begin

　　readln(n);

　　for i:=1 to n do

　　begin

　　for j:=1 to n do

　　begin

　　read(a[i,j]);

　　path[i,j]:=j;

　　end;

　　readln;

　　end;

　　for x:=1 to n do

　　for i:=1 to n do

　　for j:=1 to n do

　　if a[i,j]>a[i,x]+a[x,j] then

　　begin

　　a[i,j]:=a[i,x]+a[x,j];

　　path[i,j]:=path[i,x];

　　end;

　　readln(st,en);

　　writeln(a[st,en]);

　　writeln;

　　f:=st;

　　while f<> en do

　　begin

　　write(f);

　　write('-->');

　　f:=path[f,en];

　　end;

　　write(en);

　　end.

POJ1847

Tram

Time Limit: 1000MS	Memory Limit: 30000K
Total Submissions: 3700	Accepted: 1321

Description

Tram network in Zagreb consists of a number of intersections and rails connecting some of them. In every intersection there is a switch pointing to the one of the rails going out of the intersection. When the tram enters the intersection it can leave only in the direction the switch is pointing. If the driver wants to go some other way, he/she has to manually change the switch.

When a driver has do drive from intersection A to the intersection B he/she tries to choose the route that will minimize the number of times he/she will have to change the switches manually.

Write a program that will calculate the minimal number of switch changes necessary to travel from intersection A to intersection B.

Input

The first line of the input contains integers N, A and B, separated by a single blank character, 2 <= N <= 100, 1 <= A, B <= N, N is the number of intersections in the network, and intersections are numbered from 1 to N.

Each of the following N lines contain a sequence of integers separated by a single blank character. First number in the i-th line, Ki (0 <= Ki <= N-1), represents the number of rails going out of the i-th intersection. Next Ki numbers represents the intersections directly connected to the i-th intersection.Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.

Output

The first and only line of the output should contain the target minimal number. If there is no route from A to B the line should contain the integer "-1".

Sample Input

Sample Output

Source

Croatia OI 2002 Regional - Juniors #include<stdio.h>

int main()

{

int i,j,k,m,n,a,b,s,dis[120][120];

scanf("%d%d%d",&n,&a,&b);

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

dis[i][j]=999999;

for(i=1;i<=n;i++)

dis[i][i]=0;

for(i=1;i<=n;i++)

{

scanf("%d",&m);

for(j=0;j<m;j++)

{

scanf("%d",&s);

if(j==0)

dis[i][s]=0;

else

dis[i][s]=1;

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

for(k=1;k<=n;k++)

if(dis[j][k]>dis[j][i]+dis[i][k])

dis[j][k]=dis[j][i]+dis[i][k];

if(dis[a][b]==999999)

puts("-1");

else

printf("%d/n",dis[a][b]);

}

最短路徑Floyd算法-POJ1847Tram

核心思路

算法過程

時間複雜度

優缺點分析

算法實作

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希