實(shí)驗(yàn)內(nèi)容：1.熟練運(yùn)用Floyd算法；2.?熟練運(yùn)用Dijkstra算法；3.利用Matlab編程實(shí)現(xiàn)最短路的計(jì)算。

例1：已知無向圖G如下所示，試?yán)肍loyd算法求任意兩點(diǎn)間的最短路。

例2：試?yán)肈ijkstra算法求下面有向圖G中從點(diǎn)v1到v9的最短路。

實(shí)驗(yàn)原理：

Floyd算法：

1.使用范圍

①求任意兩結(jié)點(diǎn)的最短路徑；

②有向圖、無向圖、混合圖。

2.基本思想

直接在網(wǎng)絡(luò)圖的權(quán)矩陣W WW中用插入頂點(diǎn)的方法依次遞推地構(gòu)造出n nn個(gè)矩陣D ( 1 ) ， D ( 2 ) ， … ， D ( n ) D(1)，D(2)，…，D(n)D(1)，D(2)，…，D(n)，D ( n ) D(n)D(n)是網(wǎng)絡(luò)圖的最短距離矩陣，同時(shí)引入一個(gè)路由矩陣記錄任意兩點(diǎn)之間的最短路徑。

3.算法步驟

設(shè)D i j 為結(jié)點(diǎn)v i 到v j的距離；P i j為結(jié)點(diǎn)v i到v j路徑上v i 的后繼點(diǎn)；

W為權(quán)矩陣。

第1步：?i，j，D ij=W ij,P ij=j，k=1；(賦初值)

第2步：?i，j，若D i k + D k j < D i j，則D i j = D i k + D k j，P i j = P i k，k = k+1(更新D，PD，PD，P)

第3步：重復(fù)第2步，直到k=n+1。

Dijkstra算法：

算法特點(diǎn)：

迪科斯徹算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖或者無向圖的單源最短路徑問題，算法最終得到一個(gè)最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個(gè)子模塊。

算法的思路：

Dijkstra算法采用的是一種貪心的策略，聲明一個(gè)數(shù)組dis來保存源點(diǎn)到各個(gè)頂點(diǎn)的最短距離和一個(gè)保存已經(jīng)找到了最短路徑的頂點(diǎn)的集合：T，初始時(shí)，原點(diǎn) s 的路徑權(quán)重被賦為 0 （dis[s] = 0）。若對(duì)于頂點(diǎn) s 存在能直接到達(dá)的邊（s,m），則把dis[m]設(shè)為w（s, m）,同時(shí)把所有其他（s不能直接到達(dá)的）頂點(diǎn)的路徑長度設(shè)為無窮大。初始時(shí)，集合T只有頂點(diǎn)s。

然后，從dis數(shù)組選擇最小值，則該值就是源點(diǎn)s到該值對(duì)應(yīng)的頂點(diǎn)的最短路徑，并且把該點(diǎn)加入到T中，OK，此時(shí)完成一個(gè)頂點(diǎn)。

然后，我們需要看看新加入的頂點(diǎn)是否可以到達(dá)其他頂點(diǎn)并且看看通過該頂點(diǎn)到達(dá)其他點(diǎn)的路徑長度是否比源點(diǎn)直接到達(dá)短，如果是，那么就替換這些頂點(diǎn)在dis中的值。

然后，又從dis中找出最小值，重復(fù)上述動(dòng)作，直到T中包含了圖的所有頂點(diǎn)。

實(shí)驗(yàn)步驟：

1. 上機(jī)實(shí)驗(yàn)前先編寫出程序代碼

2. 錄入、編輯程序

3. 調(diào)適程序至正確運(yùn)行

4. 記錄運(yùn)行時(shí)的輸入和輸出

5. 對(duì)程序做進(jìn)一步完善

程序代碼：

例1：

d=[0 3?5?Inf Inf Inf

???3 0 1 2 2 Inf

???5 1 0 Inf 4 Inf

???Inf 2 Inf 0 2 4

???Inf 2 4 2 0 2

???Inf Inf Inf 4 2 0];

n=length(d);

U=d;

S=zeros(n,n);

for i=1:n

????for j=1:n

????????S(i,j)=j;

????end

end

for i=1:n

????for j=1:n

????????for m=1:n

????????????if U(i,j)>U(i,m)+U(m,j)

????????????????U(i,j)=U(i,m)+U(m,j);

????????????????S(i,j)=S(i,m);

????????????end

????????end

????end

end

S

U

例2：

W=input('此程序有關(guān)MST，請(qǐng)輸入權(quán)矩陣：');

?[i,j,s] = find(W);

ss = [i';j';s'];

dg = sparse(ss(1,:),ss(2,:),ss(3,:));

dg(9,9)=0;

h=view(biograph(dg,[],'ShowWeights','on'));

[dist,path,~]=graphshortestpath(dg,1,9,'Directed','true')

set(h.Nodes(path),'Color',[1 0.4 0.4]);

edges=getedgesbynodeid(h,get(h.Nodes(path),'ID'));

set(edges,'LineColor',[1 0 0]);

set(edges,'LineWidth',2);

實(shí)驗(yàn)運(yùn)行結(jié)果界面：

實(shí)驗(yàn)總結(jié)：

本次實(shí)驗(yàn)通過Floyd算法和Dijkstra算法求解了最短路徑問題，掌握了它們的基本原理和實(shí)現(xiàn)方法。Floyd算法適用于求解任意兩點(diǎn)間的最短路徑，而Dijkstra算法適用于求解從指定起點(diǎn)到指定終點(diǎn)的最短路徑。

在適用范圍上：

Floyd算法適用于求解任意兩點(diǎn)間的最短路徑，可以處理帶負(fù)權(quán)邊的圖，但不能處理帶負(fù)權(quán)回路的圖。Dijkstra算法適用于求解從指定起點(diǎn)到其他所有點(diǎn)的最短路徑，不能處理帶負(fù)權(quán)邊的圖。

在穩(wěn)定性上：

Floyd算法是一種動(dòng)態(tài)規(guī)劃算法，可以保證找到全局最優(yōu)解。但是Dijkstra算法是一種貪心算法，每次選擇當(dāng)前最短路徑的頂點(diǎn)，不能保證全局最優(yōu)解，但對(duì)于非負(fù)權(quán)圖可以保證最短路徑是最優(yōu)的。

在實(shí)現(xiàn)難度上：

Floyd算法相對(duì)簡單，只需使用三重循環(huán)更新距離矩陣即可。Dijkstra算法在實(shí)現(xiàn)時(shí)需要使用優(yōu)先隊(duì)列等數(shù)據(jù)結(jié)構(gòu)，相對(duì)復(fù)雜一些。

學(xué)到很多新的東西，路漫漫其修遠(yuǎn)兮，吾將上下而求索。加油！