急問..用C程式寫出Bellman-Ford最短路徑演算法

Question

請問我想用C程式寫出Bellman-Ford最短路徑演算法..但我查了好多資料和書本..這個演算法的資料真的好少..只有Floyd這個演算法比較常見...我目前只寫的出Floyd演算法的...想請問有人會用C程式寫出Bellman-Ford最短路徑演算法嗎?
(有回答出我的問題的第一位回答者..我會立刻選你做最佳解答!)

急問!20點!要更多點也行!

我是要讀檔的~我將我的Floyd程式寄給您~我希望跟我的程式寫的一樣(因為我要讀檔..我已經寫好了)只是變成Bellman-Ford的方法..不知道您可以幫我修改看看嗎?我將我的程式寄給您!謝謝您了~如果您願意撥空解答~我會立刻選您為最佳解答!

printf("\n\nk=1:\n");//先印出不經過任何點的路徑長度
k=1;
for(i=0; i

for(i=0;i

if(r!=i) //列不等於n..因為跟n有關的行和列值都不變
{
col=j,row=i;
for(c=0;c

else//除了左上至右下的對角線
{
if(matrix[col][row]!='9999')//不可以是走不到的
{
path+=matrix[col][row];//將路徑長度存到path
if(row!=r)//走到目的地就結束
{
col=row;
row=r;
}
else
{
c=count;
}
}

else//走不到的就立刻結束
{
c=count;
}
}
}
if(matrix[col][row]!='9999'&&path

printf("k=%d(最短路徑解):\n",(count-1));//印出最後的結果的矩陣
for(i=0; i

scanf("%c",&c);//延遲執行畫面以方便檢視
system("pause");
return 0;

已經將我寫的程式碼主要部分po上來囉~請問有辦法幫我改成Bellman-Ford的方法嗎?若可以的話我會立刻選您為最佳解答!真的很感謝^^

Answer 1

因為你沒有給詳細的條件，所以我寫虛擬碼，如果有需要詳細的程式碼的話我再補充

先定代號XXX代表無限大
input:
n, 節點的數目
V，節點的集合
E，邊的集合
(u, v)，節點u到節點v的邊
w，路徑長度的函數，w(u, v)代表點u到點v的距離，假使u到v沒有邊的話則
　w(u,v) = XXX
s，起始節點

程式：
===============================================
for each u in V
　d[u] = XXX
d[s] = 0

for i = 1 to n - 1
　do for each edge (u,v) in E
　　do if d[v] > d[u] + w(u, v)
　　　d[v] = d[u] + w(u, v)

for each edge(u, v) in E
　do if d[v] > d[u] + w(u, v)
　　then return false
return true
===============================================

程式結束後d[v]代表s到v的最短距離，如果程式回傳值是false代表input含有路徑長為負的cycle

這個演算法的好處是有邊長為負的邊也可以使用，而且可以偵測是否含有負的迴圈

2006-08-02 03:00:19 補充：
我的信箱:[e-mail]

Answer 2

http://en.wikipedia.org/wiki/Bellman-Ford
它能不能解決你的問題?