所有頂點對最短路徑問題（圖的應用）

醫院選址：4個村莊之間的交通圖如圖1所示，村莊之間的距離為圖中各邊上的權值。現在要從這4個村莊中選擇一個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院最近。

（PS:具體問題見附件）

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

<code>#include&lt;iostream&gt;</code>

<code>using</code> <code>namespace</code> <code>std;</code>

<code>int</code> <code>main(){</code>

<code>int</code> <code>h,i,j,minn=10000;</code>

<code>int</code> <code>a[1][4][4]={{{0,7,10000,5},{10000,0,4,10000},{6,6,0,10000},{8,10000,6,0}}},b[100][4][4]={{{0,7,10000,5},{10000,0,4,10000},{6,6,0,10000},{8,10000,6,0}}},c[4]={0};</code>

<code>//b數組使用三維來表示一次次的疊代結果，c數組來表示其他村子到一個村子的最遠距離，[0][0]表示A-&gt;A,[0][1]表示A-&gt;B,其他類推</code>

<code>//以下是Floyd算法求最短路問題</code>

<code>for</code><code>(h=0;h&lt;100;h++){</code>

<code>for</code><code>(i=0;i&lt;4;i++){</code>

<code>for</code><code>(j=0;j&lt;4;j++){</code>

<code>int</code> <code>k=10000;</code>

<code>for</code><code>(</code><code>int</code> <code>m=0;m&lt;4;m++){</code>

<code>if</code><code>(k&gt;b[h][i][m]+a[0][m][j])</code>

<code>k=b[h][i][m]+a[0][m][j];</code>

<code>}</code>

<code>b[h+1][i][j]=k;</code>

<code>//其他村子到每個村子的最遠距離</code>

<code>if</code><code>(b[9][i][j]&gt;c[j])</code>

<code>c[j]=b[h][i][j];</code>

<code>//minn表示這些最遠距離中的最小值</code>

<code>if</code><code>(c[i]&lt;minn)</code>

<code>minn=c[i];</code>

<code>if</code><code>(minn==c[0])</code>

<code>cout&lt;&lt;</code><code>"建立在A村"</code><code>&lt;&lt;endl;</code>

<code>else</code> <code>if</code><code>(minn==c[1])</code>

<code>cout&lt;&lt;</code><code>"建立在B村"</code><code>&lt;&lt;endl;</code>

<code>else</code> <code>if</code><code>(minn==c[2])</code>

<code>cout&lt;&lt;</code><code>"建立在C村"</code><code>&lt;&lt;endl;</code>

<code>else</code>

<code>cout&lt;&lt;</code><code>"建立在D村"</code><code>&lt;&lt;endl;</code>

<code>cout&lt;&lt;</code><code>"此時距離醫院最遠村子到醫院的距離為："</code><code>&lt;&lt;minn&lt;&lt;endl;</code>

<code>return</code> <code>0;</code>

 本文轉自 pangfc 51CTO部落格，原文連結：http://blog.51cto.com/983836259/1338193，如需轉載請自行聯系原作者