单源最短路径Bellman-Ford算法 - c++编程基础

int MSWBellmanFord::BellmanFindKey(char key)
{
int i;
for(i = 0;i < bfordGraph->vertexnum;i++)
{
if(bfordGraph->vertexs[i].key == key)
break;
}
return i;
}

void MSWBellmanFord::BellmanInitSingleSource()
{
int vernum = bfordGraph->vertexnum;
for(int i = 0;i < vernum;i++)
{
swayweight[i] = MAXVALUE;
parent[i] = i;
}
}

bool MSWBellmanFord::BellmanMSW(char sourceKey)
{
int location = BellmanFindKey(sourceKey);
int vernum = bfordGraph->vertexnum;
int i,j;
Edge *temp;
BellmanInitSingleSource();
//swayweight[0] = 0; //这里为了偷懒，没有随意指定source，location本来是代表source的下标的
swayweight[location] = 0;
for(i = 0;i < vernum; i++)
{
/*
for(j = 0;j < vernum; j++)
{
temp = bfordGraph->vertexs[j].adj;
while(temp != NULL)
{
if((temp->weight + swayweight[j]) < swayweight[temp->verno])
{
swayweight[temp->verno] = temp->weight + swayweight[j];
parent[temp->verno] = j;
}
temp = temp->next;
}
}
*/
temp = bfordGraph->vertexs[location].adj;
while(temp != NULL)
{
if((temp->weight + swayweight[location]) < swayweight[temp->verno])
{
swayweight[temp->verno] = temp->weight + swayweight[location];
parent[temp->verno] = location;
}
temp = temp->next;
}
j = (location + 1) % vernum;
while(j != location)
{
temp = bfordGraph->vertexs[j].adj;
while(temp != NULL)
{
if((temp->weight + swayweight[j]) < swayweight[temp->verno])
{
swayweight[temp->verno] = temp->weight + swayweight[j];
parent[temp->verno] = j;

}
temp = temp->next;
}
j = (j + 1) % vernum;
}

}

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;
}

#include
#include
using n

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