bellmanford.cpp

bellman-ford的实现。可以输出每条最短路径经过的节点

#include"bellmanford.h"
#include<fstream>
using namespace std;
void Initialize_Single_Source(ALGraph& G,VNode& s)//初始化
{
    for(int i=0; i<G.vexnum; i++)
    {
        G.vertices[i].father = NULL;
        G.vertices[i].d = max;    
    }
    s.d = 0;
}

void Relax(VNode& v, VNode& w, ArcNode * p)//Relax操作,更新最短路径
{
    if (w.d > v.d+ p->weight)
    {
        w.d = v.d+ p->weight;
        w.father = &v;
    }
}

bool Bellman_Ford(ALGraph& G, VNode& s)
{
    ArcNode * p;
    int i;
    
    Initialize_Single_Source(G, s);

    for (int j=0; j<G.vexnum-1; j++)//V-1趟Relax
    {
        for(i=0; i<G.vexnum; i++)//沿着头结点
        {
            for (p=G.vertices[i].firstarc; p!=NULL; p=p->nextarc)//沿着表结点
            {            
                Relax(G.vertices[i], G.vertices[p->adjvex], p);
            }
        }
    }
    //判断是否有负回路
    for(i=0; i<G.vexnum; i++)//沿着头结点
    {
        for (p=G.vertices[i].firstarc; p!=NULL; p=p->nextarc)//沿着表结点
        {
            if (G.vertices[p->adjvex].d > G.vertices[i].d+ p->weight) 
            {
                cout<<"图中有负权值回路."<<endl;
                return false;
            }
        }
    }

    return true;  
}
int get_node_index(ALGraph &G,char c){
	//cout<<G.vexnum<<"hhahahah"<<endl;
	for(int i = 0; i < G.vexnum;i++){
		if (G.vertices[i].value == c)
			return i;
	}
	return -1;
}
void ArcAdd(ALGraph &G,char x,char y, int weight)
{
 int m = get_node_index(G,x);
 int n = get_node_index(G,y);
 //cout<<x<<y<<m<<n<<endl;
 
 ArcNode *p,*h,*q;
 p=new ArcNode;
 p->adjvex=m;
 p->nextarc=NULL;
 p->weight = weight;
 h=q=G.vertices[n].firstarc;
 if(q==NULL){
  G.vertices[n].firstarc=p;  
}
 else
 {
  if((p->adjvex)>(q->adjvex))
  {
   p->nextarc=q;
   G.vertices[n].firstarc=p;
  }
  else
  {
   while(G.vertices[n].firstarc!=NULL&&q->nextarc!=NULL&&(p->adjvex)<(q->adjvex))//????????????????
   {
    h=q;
    q=q->nextarc;
   }
   if(q->nextarc==NULL&&(p->adjvex)<(q->adjvex))
   {
    q->nextarc=p;
   }
   else
   {
    p->nextarc=q;
    h->nextarc=p;
   }
  }
 }
}
void createGraph(ALGraph & g){
	ifstream in_file("c:/graph_data.txt");
	
	if(!in_file){
          cout<<"file error"<<endl;
          exit(1);
    }
	in_file >> g.vexnum;
	AdjList vertices = new VNode[g.vexnum];
	for (int i = 0; i < g.vexnum;i++){
        //cout<<i<<endl;
		vertices[i].adjvex = i;
		vertices[i].d = 0;
		vertices[i].father = NULL;
		vertices[i].firstarc = NULL;
		in_file >> vertices[i].value;
		
	}
	g.vertices = vertices;
	in_file >> g.arcnum;
	for(int j = 0;j < g.arcnum;j++){
		char m,n;
        int w;
		in_file >> n >> m >> w;
		ArcAdd(g,m,n,w);
	}
	in_file.close();

}




void ClearUp(ALGraph &G)//销毁图G
{
    ArcNode* p = NULL;    
    ArcNode* q = NULL;
    int i;
    for(i=0; i<G.vexnum; i++)  //回收表结点
    {    
        p = G.vertices[i].firstarc;
        while (p != NULL) 
        {
            q = p->nextarc;
            delete p;
            p = q;            
        }
    }

    delete [] G.vertices;     //回收头结点
    G.vertices = NULL;
    G.arcnum = 0;
    G.vexnum = 0;
}


void PrintPath(ALGraph G, VNode s, VNode v)//递归打印最短路径
{    
    if (v.father != NULL)
    {
        PrintPath(G, s, *v.father);
        cout<<"v"<<v.adjvex<<"→";
    }
    else
        cout<<"v"<<s.adjvex<<"→";  
}



int main(){
	ALGraph g;
	 createGraph(g);
	 
	 //第二个参数是源。
	 Bellman_Ford(g, g.vertices[0]);
	 
     for(int i = 0;i < 5;i++){
             cout<<g.vertices[i].d<<"\t";
     }
	 cout<<endl;

	 PrintPath(g, g.vertices[0], g.vertices[0]);
	 cout<<endl;
	 PrintPath(g, g.vertices[0], g.vertices[1]);
	 cout<<endl;
	 PrintPath(g, g.vertices[0], g.vertices[2]);
	 cout<<endl;
	 PrintPath(g, g.vertices[0], g.vertices[3]);
	 cout<<endl;
	 PrintPath(g, g.vertices[0], g.vertices[4]);
	 cout<<endl;
	 ClearUp(g);
	 
	 
	 return 0;
}