dijkstra.cpp

单源最短路径问题：给定带权有向图G=(V,E)。给定V中的一个顶点v

#include"iostream.h"
//单源最短路径问题：给定带权有向图G=(V,E)。给定V中的一个顶点v，称为源。要计算从源到所有其它各顶点的最短路径长度。
void dijkstra(int v,float a[],float dist[], int prev[], int n, float max_value){
	//v 为源点，a[i*n+j]表示边(i,j)的权值，当不存在边(i,j)时，a[i*n+j]=max_value
	//dist[i]存储当前 源到顶点i的最短路径长度，prev[i]表示由源点v到顶点i的最短路径中i的前继顶点
	int i, j;
	float temp;
	float newdist;
	if(v < 0 || v >= n) return;
	bool *s=new bool[n];
	for(i = 0; i < n; i++){//计算dist
		dist[i] = a[v * n + i];
		s[i] = false;
		if(dist[i] == max_value) prev[i] = n;
		else prev[i] = v;
	}
	dist[v] = 0; s[v] = true;

	for(i = n-1; i > 0; i--){//每次添加一个顶点
		temp = max_value;
		int u = v;
		for(j = 0; j < n; j++){
			if((!s[j]) && dist[j] < temp){
				u = j;
				temp = dist[j];
			}
		}
		s[u] = true;

		for(j = 0; j < n; j++){//更新dist
			if((!s[j]) && a[u * n + j] < max_value){
				newdist = dist[u] + a[u * n + j];
				if(newdist < dist[j]){
					dist[j] = newdist;
					prev[j] = u;
				}
			}
		}
	}
	delete []s;
}

void main()
{
	int i,j;
	int n=5;//V={0,1,2,3,4}
	int v=0;
	float max_value =  1000000;
	float *a = new float[n*n]; 
	float *dist=new float[n];
	int *prev = new int[n];
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			a[i*n+j]=max_value;
			if(i==j)
				a[i*n+j]=0;
		}
	}
	a[1]=10;a[3]=30;a[4]=100;//E={(0,1,10),(0,3,30),(0,4,100),(1,2,50),(2,4,10),(3,2,20),(3,4,60)}
	a[n+2]=50;
	a[n*2+4]=10;
	a[n*3+2]=20;a[n*3+4]=60;
	dijkstra(v,a,dist,prev,n,max_value);
	for(i=0;i<n;i++){
		cout<<"dist["<<i<<"]: "<<dist[i]<<";";
		cout<<"prev["<<i<<"]: "<<prev[i]<<endl;
	}
}