单源最短路径Bellman-Ford算法 (三)

for(j = 0;j < vernum; j++)
{
temp = bfordGraph->vertexs[j].adj;
while(temp != NULL)
{
if((temp->weight + swayweight[j]) < swayweight[temp->verno])
{
return false;
}
temp = temp->next;
}
}
return true;
}

void MSWBellmanFord::BellmanOutput()
{
int i,j,weight;
list route;
cout<<"All the most shortest route from source : "< for(i = 0;i < bfordGraph->vertexnum;i++)
{
j = i;
weight = swayweight[j];
do
{
route.push_front(j);
j = parent[j];

}while(parent[j] != j);

cout<vertexs[j].key;
cout<<"---"<vertexs[route.front()].key;
route.pop_front();
while(!route.empty())
{
if(route.front() != j)
cout<<"---"<vertexs[route.front()].key;
route.pop_front();
}
cout<<" "< }

}

int main()
{
char vertex[] = {'S','T','X','Y','Z'};
int vernum = 5;
char adj[][2] = {{'S','T'},{'S','Y'},{'T','X'},{'T','Y'},{'T','Z'},{'X','T'},{'Y','X'},{'Y','Z'},{'Z','S'},{'Z','X'}};
int weight[] = {6,7,5,8,-4,-2,-3,9,2,7};
int adjnum = 10;
MSWBellmanFord *bellford = new MSWBellmanFord(vertex,vernum,adj,weight,adjnum);
bellford->BellmanMSW('S');
bellford->BellmanOutput();

return 0;
}
结果如下：

[cpp]
All the most shortest route from source :
S---S 0
S---Y---X---T 2
S---Y---X 4
S---Y 7
S---Y---X---T---Z -2
请按任意键继续. . .

All the most shortest route from source :
S---S 0
S---Y---X---T 2
S---Y---X 4
S---Y 7
S---Y---X---T---Z -2
请按任意键继续. . .