c++ - 最短路径实现问题

我正在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

打印的第一套是正确的。更新部分出了点问题。我似乎无法弄清楚。

编辑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;

}

以下是我的输入代码

最佳答案

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

例如，这里的ShortestPathArray [a] = a = 1 = 2147483647;即最大范围，并且在此值中您添加了更多值，因此超出了范围。
尝试使用比最大限制小的值。