算法導論 第二十四章：單源最短路徑

在單源路徑問題中常涉及到松弛技術（Relaxation）,其原理如下：

Bellman-Ford 算法

該算法主要是解決邊的權重可能為負的情況。

僞代碼如下：

EG:

運作時間：O(VE)。

Bellman-Ford 算法的一個重要應用是差分限制（Difference and Constraints），其原理如下：

對于一個差分限制Ax<b，可以将其轉換為限制圖，然後通過Bellman-Ford算法求解源點到圖中其他點的最短路徑，其解也即該差分限制系統的解。如：

有像無循環圖中的單源路徑

僞代碼：

EG:

運作時間：O(V+E)。

Dijkstra 算法

僞代碼：

EG:

運作時間：

若用數組存儲，則 T=O(V²)

若用二項式堆存儲，則T=O((V+E)lgV)

若用斐波拉契堆存儲，則T=O(E+VlgV)

===============================================================================================================================

Bellman-Ford算法完整代碼：

#include<iostream>
#include<climits>
using namespace std;

typedef char vType;

typedef struct edge{
	vType vs;
	vType ve;
	int weight;
	}edge;
typedef struct gVertex{
	vType key;
	vType parent;  //the parent of this node
	int d;            //discovered time
	}gVertex;
typedef struct gEdge{
	gVertex *u;
	gVertex *v;
	int w;
	}gEdge;
typedef struct Graph{
	int vNum;
	int eNum;
	gVertex *V;
	gEdge *E;
	int kind;    //the type of the Graph
	}Graph;
void Graph_Init(Graph &G,vType *V,edge *E,int vNum,int eNum)
{
	G.vNum = vNum;
	G.eNum = eNum;
	G.V = new gVertex[G.vNum];
	G.E = new gEdge[G.eNum];
	for(int i=0; i<vNum; i++)
		G.V[i].key=V[i];
	for(int i=0; i<eNum; i++)
	{
		gVertex *sNode = new gVertex();
		gVertex *eNode = new gVertex();
		sNode->key = E[i].vs;
		eNode->key = E[i].ve;
		G.E[i].u = sNode;
		G.E[i].v = eNode;
		G.E[i].w = E[i].weight;
		}
	}
int Locate(Graph &G,vType s)
{
	for(int i=0; i<G.vNum; i++)
		if(s == G.V[i].key)
			return i;
	return -1;
	}
void Graph_Print(Graph &G)
{
	for(int i=0; i<G.vNum; i++)
		cout<<G.V[i].parent<<"   "<<G.V[i].key<<"   "<<G.V[i].d<<endl;
}
void Init_SingleSource(Graph &G,vType s)
{
	for(int i=0; i<G.vNum; i++){ 
		G.V[i].d = INT_MAX;
		G.V[i].parent = '0';
		} 
	int s_i = Locate(G,s);
	G.V[s_i].d = 0;
		
	}
void Graph_edgeRelax(gVertex *u,gVertex *v,int w){
	//noting:if u->d or u->d + w >= INF,it will overflow
	if(u->d == INT_MAX || u->d + w >= INT_MAX)
			return ;
	if(v->d  > u->d + w){
		v->d = u->d + w;
		v->parent = u->key;
		}  
	}
int Graph_BellmanFord(Graph &G,vType s){
	Init_SingleSource(G,s);
	//swap the starting node with the first node in G.V
	int s_i=Locate(G,s);
	gVertex *temp = new gVertex();
	*temp = G.V[s_i];
	G.V[s_i]=G.V[0];
	G.V[0] = *temp;
	
	//for every node,relax eNum edges
	for(int i=1; i<G.vNum; i++){
		for (int j=0; j< G.eNum; j++){
			int u_j = Locate(G,(G.E[j].u)->key);
			int v_j = Locate(G,(G.E[j].v)->key);
			gVertex *uNode = &G.V[u_j];
			gVertex *vNode = &G.V[v_j];
			Graph_edgeRelax(uNode,vNode,G.E[j].w);		
		 	}
		cout<<"Every round:"<<endl;
		Graph_Print(G);
		} 

	for(int j=0; j<G.eNum; j++ ){
		int u_j = Locate(G,(G.E[j].u)->key);
		int v_j = Locate(G,(G.E[j].v)->key);
		gVertex *uNode = &G.V[u_j];
		gVertex *vNode = &G.V[v_j];
		cout<<"uNode->d="<<uNode->d<<"   vNode->d="<<vNode->d<<"   w="<<G.E[j].w<<endl;
		if(vNode->d > uNode->d + G.E[j].w)
			return -1;
 	}
	return 1;	
	}
int main()
{
	vType V[]={'s','t','y','x','z'};
	 edge  E[]={{'s','t',6},{'s','y',7},{'t','y',8},{'t','x',5},
			   {'t','z',-4},{'y','x',-3},{'y','z',9},{'x','t',-2},
			   {'z','x',7},{'z','s',2}
		 		};
	int vNum = sizeof(V)/sizeof(vType);
	int eNum = sizeof(E)/sizeof(edge) ;

	Graph G;
	Graph_Init(G,V,E,vNum,eNum);
	vType s;
	cout<<"Please input the starting position:";
	cin>>s;
	if(Graph_BellmanFord(G,s)==1)
	{ 
		cout<<"The shortest-paths tree is:"<<endl;
		Graph_Print(G);
		}

	return 0;
}
           

運作結果：

DAG 單源最短路徑完整代碼：

#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<climits>
using namespace std;

#define UDG 0
#define DG  1

#define WHITE 0  
#define GRAY  1  
#define BLACK 2  
  
#define NONE 0  
#define TREE 1  
#define BACK 2  
#define FORWARD 3  
#define CROSS 4 


typedef char vType;
typedef struct gEdge{
	vType adjVertex;   //the adjacency vertex pointed by this edge.
	int weight;        //the weight of this edge
	int type;          //the type of edge
	gEdge *nextEdge;   //Point to the next edge
	}gEdge;

typedef struct gVertex{
	vType key;         // the key of the vertex
	int color;
	int d,f;           // the discovered time and the finished time
	vType parent;         // the parent node's key after searching
	gEdge *firstEdge;  // point to the first edge attached to the vertex;
	}gVertex;
typedef struct ALGraph{
	int vNum;
	int eNum;
	int kind;   //the kind of Graph 
	gVertex *HeadVertex;	
	}ALGraph;

typedef struct edge{
	vType start;
	vType end;
	int weight;
	}edge;
int Locate(ALGraph &G,vType s)
{//locate the start vertex of one edge in head vertex of the graph
	for(int i=0;i<G.vNum;i++)
		if(G.HeadVertex[i].key == s)
			return i;
	return -1;
	}
void LinkEdgeToGraph(ALGraph &G, edge e)
{
		gEdge *arc=new gEdge();
		arc->adjVertex=e.end;
		arc->weight = e.weight;

		int headV_i=Locate(G,e.start);
			
		arc->nextEdge=G.HeadVertex[headV_i].firstEdge;
		G.HeadVertex[headV_i].firstEdge = arc;
	}
void Graph_Create(ALGraph &G, vType V[], edge E[])
{
	//init the head vertex
	G.HeadVertex= new gVertex[G.vNum];
	for( int i=0;i<G.vNum;i++){
		G.HeadVertex[i].key=V[i];
		G.HeadVertex[i].firstEdge=NULL;
	}   

	//add edge to head vertex in order to create a graph
	if(G.kind == DG) //undirected graph
		for(int i=0; i<G.eNum; i++)
			LinkEdgeToGraph(G,E[i]);
	if(G.kind == UDG) // directed graph
		for(int i=0; i<G.eNum; i++)
		{
			LinkEdgeToGraph(G,E[i]);
			// link again after reversed
			edge temp;
			temp.start = E[i].end;
			temp.end   = E[i].start;
			temp.weight= E[i].weight;
			LinkEdgeToGraph(G,temp);
		 	}
	}
void ALGraph_Print(ALGraph G)
{
	for(int i=0; i<G.vNum; i++)
	{ 
		cout<<G.HeadVertex[i].key;
		gEdge *p = G.HeadVertex[i].firstEdge;
		while(p != NULL)
		{
			cout<<" -->  "<< p->adjVertex;
			p = p->nextEdge;
 		 	}  
		cout<<endl;
 		 }
	}
/*
void EdgeType_Print(ALGraph G)
{
	for(int i=0; i<G.vNum; i++)
	{
		gEdge *p = G.HeadVertex[i].firstEdge;
		while(p)
		{
			cout<<G.HeadVertex[i].key<<"-->"<<p->adjVertex<<":";
			switch(p->type)
			{
				case TREE:
					cout<<"Tree edge"<<endl;
					break;
				case BACK:
					cout<<"Back edge"<<endl;
					break;
				case FORWARD:
					cout<<"Forward edge"<<endl;
					break;
				case CROSS:
					cout<<"Cross edge"<<endl;
					break;
	 			}
			p = p->nextEdge;
	 		}
	 	}
	}
*/

/*--------------------DFS Alogithms-----------------------*/
int time0;
int r_i=0;
void Graph_DFSVisit(ALGraph &G, gVertex *u, vType *r)
{
	time0 = time0 +1;  //white vertex u has just been discovered
	u->d = time0 ;
	u->color = GRAY;
	

	gEdge *p = u->firstEdge;
	while(p)
	{ 
		vType v = p->adjVertex;
		int h_i=Locate(G,v);
		gVertex *hv = &G.HeadVertex[h_i];
		
		//classify the edge and recursive searching
		if( hv->color == WHITE)
	 	{ 
			hv->parent = u->key;
			Graph_DFSVisit(G,hv,r);
			p->type = TREE;        //Tree edge
			}
		else if(hv->color == GRAY){
			p->type = BACK;        //Back edge
		}
		else if(hv->color == BLACK)
		{
			if(u->d < hv->d)
				p->type = FORWARD; //Forward edge
			else
				p->type = CROSS;  //Cross edge
			}
		p = p->nextEdge;
		}

	u->color = BLACK;  //backen u;it is finished
	r[r_i++]=u->key;   //store the dfs result into array r

	time0 = time0 +1;
	u->f = time0;
}
void ALGraph_DFS(ALGraph &G, vType *result)
{
	//init all the vertex
	gVertex *u;
	for(int i=0; i<G.vNum; i++)
	{
		u = &G.HeadVertex[i];
		u->color = WHITE;
		u->parent = '0';
	 	} 
	time0 = 0;  //time stamp
	
	//explore every vertex
	for(int i=0; i<G.vNum; i++)
	  {
		u = &G.HeadVertex[i];
		if(u->color == WHITE)
			Graph_DFSVisit(G,u,result);
		} 
	}
/*------------------------------------------------------*/

/*-----------------Topological Sort--------------------*/
bool compare(const gVertex &a,const gVertex &b)
{
	return a.f > b.f;           //descending order 
	}
void ALGraph_TSort(ALGraph &G)
{
	vType *r = new vType[G.vNum];
	ALGraph_DFS(G,r);

	//sorting the finished time in descending order
	sort(G.HeadVertex,G.HeadVertex+G.vNum,compare);  //call the system's sorting function:

		
	}
/*-------------------------------------------------------*/
/*---------------DAG Shortest-Path-----------------------*/ 
void ShortestPath_Print(ALGraph &G)
{
	for(int i=0; i<G.vNum; i++)
	{
		cout<<G.HeadVertex[i].parent<<"   "<<G.HeadVertex[i].key<<"   "<<G.HeadVertex[i].d<<endl;
		}
	}
void Init_SingleSource(ALGraph &G,vType s)
{
	for(int i=0; i<G.vNum; i++){ 
		G.HeadVertex[i].d = INT_MAX;
		G.HeadVertex[i].parent = '0';
		} 
	int s_i = Locate(G,s);
	G.HeadVertex[s_i].d = 0;
		
	}
void Graph_edgeRelax(gVertex *u,gVertex *v,int w){
	//noting:if u->d or u->d + w >= INF,it will overflow
	if(u->d == INT_MAX || u->d + w >= INT_MAX)
			return ;
	if(v->d  > u->d + w){
		v->d = u->d + w;
		v->parent = u->key;
		}   
	}
void DAG_ShortestPath(ALGraph &G,vType s)
{
	ALGraph_TSort(G);
	Init_SingleSource(G,s);
	for(int i=0; i<G.vNum; i++)
	{
		gEdge *e = G.HeadVertex[i].firstEdge;
		while(e)
		{
			vType t = e->adjVertex;
			int v_i = Locate(G,t);
			gVertex *uNode = &G.HeadVertex[i];
			gVertex *vNode = &G.HeadVertex[v_i];
			Graph_edgeRelax(uNode,vNode,e->weight);
			
			e = e->nextEdge;
			}
		}
	}
int main(){
	vType V[]={'s','t','y','x','z','r'};
	edge E[]={{'s','x',6},{'s','t',2},{'t','x',7},
			  {'t','y',4},{'t','z',2},{'x','y',-1},
			  {'x','z',1},{'y','z',-2},{'r','s',5},
			  {'r','t',3}
			};
	ALGraph G;
	G.vNum = sizeof(V)/sizeof(vType);
	G.eNum = sizeof(E)/sizeof(edge);
	G.kind = DG;
	Graph_Create(G,V,E);
	cout<<"Please input the starting node:";
	vType s;
	cin>>s;
	DAG_ShortestPath(G,s);
	cout<<"The shortest-paths tree is:"<<endl;
	ShortestPath_Print(G);
	return 0;
	}
           

運作結果：

Dijstra算法完整代碼：

#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<climits>
#include<vector>
#include<queue>
#include<functional>
using namespace std;

#define UDG 0
#define DG  1

#define WHITE 0  
#define GRAY  1  
#define BLACK 2  
  
#define NONE 0  
#define TREE 1  
#define BACK 2  
#define FORWARD 3  
#define CROSS 4 


typedef char vType;
typedef struct gEdge{
	vType adjVertex;   //the adjacency vertex pointed by this edge.
	int weight;        //the weight of this edge
	int type;          //the type of edge
	gEdge *nextEdge;   //Point to the next edge
	}gEdge;

typedef struct gVertex{
	vType key;         // the key of the vertex
	int color;
	int d,f;           // the discovered time and the finished time
	vType parent;         // the parent node's key after searching
	gEdge *firstEdge;  // point to the first edge attached to the vertex;
	}gVertex;
typedef struct ALGraph{
	int vNum;
	int eNum;
	int kind;   //the kind of Graph 
	gVertex *HeadVertex;	
	}ALGraph;

typedef struct edge{
	vType start;
	vType end;
	int weight;
	}edge;
int Locate(ALGraph &G,vType s)
{//locate the start vertex of one edge in head vertex of the graph
	for(int i=0;i<G.vNum;i++)
		if(G.HeadVertex[i].key == s)
			return i;
	return -1;
	}
void LinkEdgeToGraph(ALGraph &G, edge e)
{
		gEdge *arc=new gEdge();
		arc->adjVertex=e.end;
		arc->weight = e.weight;

		int headV_i=Locate(G,e.start);
			
		arc->nextEdge=G.HeadVertex[headV_i].firstEdge;
		G.HeadVertex[headV_i].firstEdge = arc;
	}
void Graph_Create(ALGraph &G, vType V[], edge E[])
{
	//init the head vertex
	G.HeadVertex= new gVertex[G.vNum];
	for(  int i=0;i<G.vNum;i++){
		G.HeadVertex[i].key=V[i];
		G.HeadVertex[i].firstEdge=NULL;
	}   

	//add edge to head vertex in order to create a graph
	if(G.kind == DG) //undirected graph
		for(int i=0; i<G.eNum; i++)
			LinkEdgeToGraph(G,E[i]);
	if(G.kind == UDG) // directed graph
		for(int i=0; i<G.eNum; i++)
		{
			LinkEdgeToGraph(G,E[i]);
			// link again after reversed
			edge temp;
			temp.start = E[i].end;
			temp.end   = E[i].start;
			temp.weight= E[i].weight;
			LinkEdgeToGraph(G,temp);
		 	}
	}
void ALGraph_Print(ALGraph G)
{
	for(int i=0; i<G.vNum; i++)
	{ 
		cout<<G.HeadVertex[i].key;
		gEdge *p = G.HeadVertex[i].firstEdge;
		while(p != NULL)
		{
			cout<<" -->  "<< p->adjVertex;
			p = p->nextEdge;
 		  	}  
		cout<<endl;
 		  }
	}
/*--------------------DFS Alogithms-----------------------*/
int time0;
int r_i=0;
void Graph_DFSVisit(ALGraph &G, gVertex *u, vType *r)
{
	time0 = time0 +1;  //white vertex u has just been discovered
	u->d = time0 ;
	u->color = GRAY;
	

	gEdge *p = u->firstEdge;
	while(p)
	{ 
		vType v = p->adjVertex;
		int h_i=Locate(G,v);
		gVertex *hv = &G.HeadVertex[h_i];
		
		//classify the edge and recursive searching
		if( hv->color == WHITE)
	 	{ 
			hv->parent = u->key;
			Graph_DFSVisit(G,hv,r);
			p->type = TREE;        //Tree edge
			}
		else if(hv->color == GRAY){
			p->type = BACK;        //Back edge
		}
		else if(hv->color == BLACK)
		{
			if(u->d < hv->d)
				p->type = FORWARD; //Forward edge
			else
				p->type = CROSS;  //Cross edge
			}
		p = p->nextEdge;
		}

	u->color = BLACK;  //backen u;it is finished
	r[r_i++]=u->key;   //store the dfs result into array r

	time0 = time0 +1;
	u->f = time0;
}
void ALGraph_DFS(ALGraph &G, vType *result)
{
	//init all the vertex
	gVertex *u;
	for(int i=0; i<G.vNum; i++)
	{
		u = &G.HeadVertex[i];
		u->color = WHITE;
		u->parent = '0';
	 	} 
	time0 = 0;  //time stamp
	
	//explore every vertex
	for(int i=0; i<G.vNum; i++)
	  {
		u = &G.HeadVertex[i];
		if(u->color == WHITE)
			Graph_DFSVisit(G,u,result);
		} 
	}
/*------------------------------------------------------*/

/*-----------------Topological Sort--------------------*/
bool compare(const gVertex &a,const gVertex &b)
{
	return a.f > b.f;           //descending order 
	}
void ALGraph_TSort(ALGraph &G)
{
	vType *r = new vType[G.vNum];
	ALGraph_DFS(G,r);

	//sorting the finished time in descending order
	sort(G.HeadVertex,G.HeadVertex+G.vNum,compare);  //call the system's sorting function:

		
	}
/*-------------------------------------------------------*/
/*---------------Dijkstra Algorithm----------------------*/ 
struct cmp{
	bool operator()(gVertex *a,gVertex *b){
		return a->d > b->d;
		}
};
void Dijkstra_Print(ALGraph &G)
{
	for(int i=0; i<G.vNum; i++)
	{
		cout<<G.HeadVertex[i].parent<<"   "<<G.HeadVertex[i].key<<"   "<<G.HeadVertex[i].d<<endl;
		}
	}
void Init_SingleSource(ALGraph &G,vType s)
{
	for(int i=0; i<G.vNum; i++){ 
		G.HeadVertex[i].d = INT_MAX;
		G.HeadVertex[i].parent = '0';
		} 
	int s_i = Locate(G,s);
	G.HeadVertex[s_i].d = 0;
		
	}
void Graph_edgeRelax(gVertex *u,gVertex *v,int w){
	//noting:if u->d or u->d + w >= INF,it will overflow
	if(u->d == INT_MAX || u->d + w >= INT_MAX)
			return ;
	if(v->d  > u->d + w){
		v->d = u->d + w;
		v->parent = u->key;
 		}   
	}
/*
void Queue_Print(priority_queue<gVertex*,vector<gVertex*>,cmp> q)
{
	while(!q.empty())
	{
		gVertex *t = q.top();
		cout<<t->key<<"   "<<t->d<<endl;
		q.pop();
 		}
}
*/
void Graph_Dijkstra(ALGraph &G,vType s)
{
	Init_SingleSource(G,s);
	priority_queue<gVertex*,vector<gVertex*>,cmp> Q;
	//clear queue Q
	for(int i=0; i<G.vNum; i++)
		Q.push(&G.HeadVertex[i]);
	
	//relax every edge just once
	vector<gVertex*> S;//restore the result
	while(!Q.empty()){
		//Extract minimum of the Queue
		gVertex *uNode = Q.top();
		Q.pop();

		S.push_back(uNode);
		int u_i = Locate(G,uNode->key);
		gEdge *e = G.HeadVertex[u_i].firstEdge;
		while(e)
		{
			vType v = e->adjVertex;
			int v_i = Locate(G,v);
			gVertex *vNode = &G.HeadVertex[v_i];
			Graph_edgeRelax(uNode,vNode,e->weight);

			e = e->nextEdge;
			}
		//resort priority queue Q
		priority_queue<gVertex *,vector<gVertex *>,cmp> tQ;
		while(!Q.empty()){
			tQ.push(Q.top());
			Q.pop();
			}
		Q = tQ;
		}

	}
int main(){
	vType V[]={'s','t','y','x','z'};
	 edge  E[]={{'s','t',10},{'s','y',5},{'t','y',2},{'t','x',1},
			   {'y','t',3},{'y','x',9},{'y','z',2},{'x','z',4},
			   {'z','x',6},{'z','s',7}
		 		};
	ALGraph G;
	G.vNum = sizeof(V)/sizeof(vType);
	G.eNum = sizeof(E)/sizeof(edge);
	G.kind = DG;
	Graph_Create(G,V,E);
	cout<<"Please input the starting node:";
	vType s;
	cin>>s;
	Graph_Dijkstra(G,s);
	cout<<"The shortest-paths tree is:"<<endl;
	Dijkstra_Print(G);
	return 0;
	}
           

運作結果：

【注：若有錯誤，請指正~~~】