摘 要：數(shù)據(jù)結(jié)構(gòu)是計算機學(xué)科的核心課程，有向圖是圖結(jié)構(gòu)的重要內(nèi)容之一。在計算機中如果用圖的鄰接矩陣存儲帶權(quán)有向圖，用權(quán)值表示各有向邊的長度，那么利用有向圖的最短路徑理論就可以解決交通網(wǎng)絡(luò)中的路線問題，如某個源點到其余各頂點的最短路徑以及所有頂點之間的最短路徑等等，從而達(dá)到資源最省的目的。

關(guān)鍵詞：源點；頂點；終點；有向圖；最短路徑

中圖分類號：TP391.41

1 求從某個源點到其余各頂點的最短路徑

針對上述鄰接矩陣，為了便于分析和計算機存儲，引進(jìn)一個輔助向量disc，它的每個分量disc[i]表示當(dāng)前所找到的從源點V0出發(fā)到達(dá)終點Vi的最短路徑，初態(tài)為：若從源點V0到頂點Vi沒有邊，則disc[i]為∞，用計算機中可表示的最大正數(shù)MAXNUM表示，若從源點V0到頂點Vi有邊，則disc[i]為該邊上的權(quán)值。設(shè)第一條最短路徑為，其中k滿足：

disc[k]=min{disc[i]|Vi∈V-V0}，v是G的頂點的集合。

下面求下一條最短路徑。

假設(shè)下一次要到達(dá)的終點是Vj，那么最短路徑有兩種可能，一種是，另一種是，與之相對應(yīng)，其長度可能是從V0到Vj的有向邊上的權(quán)值，也可能是disc[k]與從Vk到Vj的有向邊上的權(quán)值之和。如果S是已求得的最短路徑的終點的集合，那么下一條最短路徑必然是從源點V0出發(fā)，中間只經(jīng)過S中的頂點就可到達(dá)的那些頂點VZ（VZ∈V-S）的路徑中的一條。

所以通常情況下，下一條長度次短的最短路徑的長度必然是：

disc[k]=min{disc[i]|Vi∈V-S}

在每一次求得一條最短路徑之后，將終點Vk加入集合S，對所有的Vi∈V-S修改其disc[i]：

disc[i]=min{disc[i]，disc[k]+Edge[k][i]}

其中，Edge[k][i]是邊上的權(quán)值。

綜上所述，用程序設(shè)計語言實現(xiàn)該算法如下：

const int Numvers=100；//常量定義，圖中最大頂點個數(shù)

class Graph{ //圖的類定義

private：

int Edge[Numvers] [Numvers]；//存放圖的鄰接矩陣

int disc[Numvers]； //存放從頂點V0到其它各頂點的最短路徑長度

int path[Numvers]； //存放在最短路徑上該頂點的前一頂點號

int S[Numvers]； //已求得的在最短路徑上的頂點號

public：

void ShortestPath（int，int）；

}；

void Graph：：ShortestPath（int n， int v）{ //G是一個具有n個頂點的帶權(quán)有向圖

for（int i=0；i

disc[i]=Edge[v][i]；

S[i]=0； //已求出最短路徑的頂點集合初始化

if（i！=v disc[i]

else path[i]=-1； //路徑存放數(shù)組初始化

}

S[v]=1； disc[v]=0； //頂點V加入頂點集合

for（i=0；i

int min=MAXNUM；int u=v；

for（int j=0；j

if（！S[j] disc[j]

S[u]=1； //將頂點u加入集合S，表示它已在最短路徑上

for（int w=0；w

if（！S[w] Edge[u][w]

disc[w]=disc[u]+Edge[u][w]； path[w]=u；

}

}

}

引用上述算法，在圖1中，從頂點V0出發(fā)到其它各頂點的最短路徑的逐步求解過程如下：源點 終點

2 所有頂點之間的最短路徑

要求交通網(wǎng)絡(luò)中每一對頂點之間的最短路徑，可輪流以每一個頂點為源點，其余頂點為終點多次調(diào)用上述算法來完成。但還可以用依次加入中間頂點，取得最短路徑的方法：

（1）使用圖的鄰接矩陣存儲帶權(quán)有向圖；

（2）取任意兩個頂點Vi和Vj，其邊上的權(quán)值作為路徑長度；

（3）增加中間頂點，在增加中間頂點的過程中，總是以路徑長度較短者作為新路徑代替原路徑；

（4）修改鄰接矩陣的元素，用新取得的較短路徑長度代入。

算法如下：

定義一個n階方陣序列：Z（0），Z（1），…，Z（k），…，Z（n），

當(dāng)k=0時，Z（k）[i][j]=Edge[i][j]；

當(dāng)1≤k≤n時

Z（k）[i][j]=min{Z（k-1）[i][j]，Z（k-1）[i][k]+ Z（k-1）[k][j]}。

下面用程序設(shè)計語言實現(xiàn)該算法：

void Graph：：AllLengths（int n） { //Edge[n][n]是一個具有n個頂點的圖的鄰接矩陣。

//z[i][j]是頂點i和j之間的最短路徑長度。

//path[i][j]是相應(yīng)路徑上頂點j的前一頂點的頂點號，在求最短路徑時圖的類定義中//要修改path為path[Numvers][Numvers]。

for（int i=0；i

for（int j=0；j

z[i][j]=Edge[i][j]；

if（i< >j z[i][j]

else path[i][j]=0； //i到j(luò)無路徑

}

for（int k=0；k

for（i=0；i

for（j=0；j

if（z[i][k]+z[k][j]

z[i][j]=z[i][k]+z[k][j]；path[i][j]=path[k][j]；//縮短路徑長度，繞過k到j(luò)

}

}

參考文獻(xiàn)：

[1]許卓群.數(shù)據(jù)結(jié)構(gòu)[M].北京：中央廣播電視大學(xué)出版社，2003：226-254.

[2]左春榮.數(shù)據(jù)結(jié)構(gòu)[M].北京：中國物質(zhì)出版社，2008：99-118.

[3]殷人昆.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2010：283-286.

作者單位：營口職業(yè)技術(shù)學(xué)院，遼寧營口 115000