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

#define MAXVALUE 10000 //定义一个最长路径

//此处Prim算法的图为有向图

struct Edge
{
int verno; //邻接数组中节点编号
int weight; //权值
Edge* next; //指向下一条边
};

struct Vertex
{
Edge *adj; //所指向的节点所在边
int verno; //邻接数组中节点编号
char key; //关键字
};

struct Graph
{
Vertex *vertexs; //节点数组
int vertexnum; //节点个数
int adjnum; //边数
};

class MSWBellmanFord
{
public:
MSWBellmanFord(char *vertex,int vernum,char adj[][2],int *weight,int adjnum);
void BellmanInsert(int source,int dest,int weight);
int BellmanFindKey(char key);
void BellmanInitSingleSource();
bool BellmanMSW(char sourceKey);
void BellmanOutput();
private:
int *swayweight;
int *parent;
Graph *bfordGraph;
};

MSWBellmanFord::MSWBellmanFord(char *vertex,int vernum,char adj[][2],int *weight,int adjnum)
{
int i,source,dest;

swayweight = new int[vernum];
parent = new int[vernum];
bfordGraph = new Graph;

bfordGraph->vertexs = new Vertex[vernum];
bfordGraph->adjnum = adjnum;
bfordGraph->vertexnum = vernum;
for(i = 0;i < vernum;i++)
{
bfordGraph->vertexs[i].key = vertex[i];
bfordGraph->vertexs[i].verno = i;
bfordGraph->vertexs[i].adj = NULL;
}

for(i = 0;i < adjnum;i++)
{
source = BellmanFindKey(adj[i][0]);
dest = BellmanFindKey(adj[i][1]);
BellmanInsert(source,dest,weight[i]);
//BellmanInsert(dest,source,weight[i]); //无向图与有向图的区别在此
}
}

void MSWBellmanFord::BellmanInsert(int source,int dest,int weight)
{
if(bfordGraph->vertexs[source].adj == NULL || bfordGraph->vertexs[source].adj->weight > weight)
{
Edge* newnode = new Edge;
newnode->verno = dest;
newnode->weight = weight;
newnode->next = bfordGraph->vertexs[source].adj;
bfordGraph->vertexs[source].adj = newnode;
}
else
{
Edge* temp = bfordGraph->vertexs[source].adj;
while(temp->next != NULL) //插入新边的时候，把权值从低到高进行排序
{
if(temp->next->weight > weight)
break;
temp = temp->next;
}
Edge* newnode = new Edge;
newnode->verno = dest;
newnode->weight = weight;
newnode->next = temp->next;
temp->next = newnode;
}
}

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-