单源最短路径源代码.cpp

一个求单源最短路径的算法

#include <iostream>

#define N 5
#define MAX 200

using namespace std;

unsigned int s[N];       //集合S
unsigned int count = 0;      //集合S顶点数

//给有向图赋权值
void putValue(unsigned int i=0,unsigned int j=0,unsigned int value=MAX,unsigned ** p=0)
{
	p[i][j] = value;
}

//扩充集合S
void appendS(unsigned int a)
{
	s[count] = a;
	count++;
}

//判断元素a是否在集合s中
bool inS(unsigned int a)
{
	int i = 0;
	for(i=0;i<count;i++)
		if(s[i]==a) return true;
	return false;
}

//返回新的源点u
unsigned int getU(unsigned int dist[])
{
	unsigned int min = MAX,mark = 0;
	unsigned int i = 0;
	for(i=1;i<N;i++)
	{
		if((!(inS(i))) && dist[i]<=min)
		{
			min = dist[i];
			mark = i;
		}
	}
	return mark;
}


int main()
{
	unsigned int ** p;       //存储有向图
	unsigned int prev[N];    //存储最短路径上顶点i的前一个顶点
	unsigned int dist[N];	 //存储从源到u的最短路径
	unsigned int u;          //V-S中具有最短特殊路径的顶点u

	int i = 0,j = 0;
	
	//初始化有向图
	for(i=0;i<N;i++)
		p = new unsigned int * [N];
	for(i=0;i<N;i++)
		p[i] = new unsigned int [N];

	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
		{
			if(i==j) p[i][j] = 0;
			else p[i][j] = MAX;
		}

	//赋权值
	putValue(0,1,10,p);
	putValue(0,3,30,p);
	putValue(0,4,100,p);
	putValue(1,2,50,p);
	putValue(2,4,10,p);
	putValue(3,2,20,p);
	putValue(3,4,60,p);
	
	//初始化prev
	for(i=0;i<N;i++)
		prev[i] = 0;
	
	//初始化集合s
	for(i=0;i<N;i++)
		s[i] = 0;
	
	//初始化dist
	for(i=0;i<N;i++)
		dist[i] = p[0][i];

	u = 0;       //初始化特殊顶点u
	appendS(u);  //初始化集合S

	while(count<N)
	{
		for(j=1;j<N;j++)
		{
			if(p[u][j] + dist[u] < dist[j])
			{
				dist[j] = dist[u] + p[u][j];
				prev[j] = u;
			}
			
		}
		u = getU(dist); //取得新的具有最短特殊路径的顶点u
		appendS(u);     //扩充集合S

	}
	
	//输出源点到顶点i的单源最短路径
	for(i=0;i<N;i++)
		cout << "顶点1到顶点" << i+1 << " : " << dist[i] << endl;
	
	//具体路径
	cout << "输入目标顶点：" ;
	cin >> j;
	cout << j << " <- ";
	for(i=j-1;prev[i]>0;i=prev[i])
		cout << prev[i]+1 << " <- ";
	cout << 1 << endl;
	
	return 0;
}