最短路徑實現問題

我正在C++中實現Shortest Path Problem。基本上用戶輸入SourceVertex，函數FindShortestPath(int SourceVertex)找到並打印從SourceVertex到所有其餘頂點的最短路徑。最短路徑實現問題

void Graph::FindShortestPath(int SourceVertex) 
{ 
    cout<<"The shortest paths from "<<SourceVertex<<" are"<<endl; 
    //initialize the ShortestPathArray 
    for(int a=0;a<NumberOfVertices;a++) 
     ShortestPathArray[a]=numeric_limits<int>::max(); 
    ShortestPathArray[SourceVertex]=0; 

    for(int a=0;a<NumberOfVertices;a++) 
    { 
     if(WeightMatrix[SourceVertex][a]!=0) 
      ShortestPathArray[a]=WeightMatrix[SourceVertex][a]; 

    } 
    cout<<"Direct Edges Length"<<endl; 
    for(int a=0;a<NumberOfVertices;a++) 
    { 
     cout<<SourceVertex<<"->"<<a<<"="<<ShortestPathArray[a]<<endl; 
    } 
    cout<<"Shortest Path after updating"<<endl; 

    for(int a=0;a<NumberOfVertices;a++) 
     for(int b=0;b<NumberOfVertices;b++) 

      if(WeightMatrix[a][b]!=0)//edge exists 
      { if(ShortestPathArray[b]>(ShortestPathArray[a]+WeightMatrix[a][b])) 
      { 
       ShortestPathArray[b]= ShortestPathArray[a]+WeightMatrix[a][b];}} 

    for(int a=0;a<NumberOfVertices;a++) 
    cout<<SourceVertex<<"->"<<a<<"="<<ShortestPathArray[a]<<endl;}

我得到以下輸出

The shortest paths from 4 are 
Direct Edges Length 
4->0=2147483647 
4->1=6 
4->2=10 
4->3=4 
4->4=0 
Shortest Path after updating 
4->0=2147483647 
4->1=-2147483645 
4->2=-2147483646 
4->3=-2147483644 
4->4=-2147483647

即印刷是正確的第一組。更新部分有問題。我似乎無法弄清楚。

EDIT-1

int main(){ 

    Graph g(5); 
    g.AddEdge(0,4,2); 
    g.AddEdge(0,2,3); 
    g.AddEdge(0,1,5); 
    g.AddEdge(1,3,6); 
    g.AddEdge(1,2,2); 
    g.AddEdge(4,3,4); 
    g.AddEdge(4,1,6); 
    g.AddEdge(4,2,10); 
    g.AddEdge(2,1,1); 
    g.AddEdge(2,3,2); 
    g.FindShortestPath(4); 

    return 0; 

}

以下是我輸入代碼

來源

2014-04-14 fts

請顯示不良行爲發生的數據。 – Codor

if(WeightMatrix[a][b]!=0)//edge exists 
{ 
    if(ShortestPathArray[b]>(ShortestPathArray[a]+WeightMatrix[a][b])) 
    { 
     ShortestPathArray[b]= ShortestPathArray[a]+WeightMatrix[a][b]; 
    } 
}

這裏ShortestPathArray並[a] = 2147483647的e.g A = 0值;即最大範圍，並且在這個值中您將增加更多的值，因此它超出範圍。嘗試使用比最大限制更小的值。

來源

2014-04-14 07:09:02 Himanshu

它有幫助。當我向最大值添加更多值時，它會變成負值，因此可以增加一個abs。 – fts

是的，如果您爲最大值添加更多值，它會給出一些-ve值。很高興知道問題解決了。 :) – Himanshu

這解決了我的問題。

更改

if(WeightMatrix[a][b]!=0)//edge exists 
      { if(ShortestPathArray[b]>(ShortestPathArray[a]+WeightMatrix[a][b])) 
      { 
       ShortestPathArray[b]= ShortestPathArray[a]+WeightMatrix[a][b];}}

到

if(WeightMatrix[a][b]!=0)//edge exists 
      { if(ShortestPathArray[b]>abs(ShortestPathArray[a]+WeightMatrix[a][b])) 
      { 
       ShortestPathArray[b]= ShortestPathArray[a]+WeightMatrix[a][b];}}

添加ABS解決了這個問題。顯然ShortestPathArray的某些值是負值。如果最初的某個值是numeric_limits<int>::max()，並且我正在添加某些值，則最終結果會被包含爲負值。因此，增加了abs（）函數。

來源

2014-04-14 07:21:09 fts

'ShortestPathArray [b] = ShortestPathArray [a] + WeightMatrix [a] [b];'我認爲在這一行也應該使用'abs'.If它工作正常沒有問題。 – Himanshu

最短路徑實現問題

回答

相關問題