贪婪求单源最短路径.cpp

算法设计分析的一些例子程序....凑字数..凑字数

#include <iostream>
#define INF 10000
using namespace std;

void Dijkstra(int n,int v,int * dist,int c[5][5])
{
	bool s[5];
	for(int i=0;i<n;i++)
	{
	s[i]=false;	
	dist[i]=c[v][i];
	}
	s[v]=true;
	for( i=0;i<n-1;i++)
	{
		int t=INF;
		int u=v;
		for(int j=0;j<n;j++)
		if((!s[j])&&(dist[j]<t))
			{
				u=j;
				t=dist[j];		
			}
		s[u]=true;
			for( j=0;j<n;j++)
				if((!s[j])&&c[u][j]<INF)
				{
					int newdist=dist[u]+c[u][j];
					if(newdist<dist[j])
					{
						dist[j]=newdist;
					}
				}
	}
	cout<<"点"<<v+1<<"到各定点最短路径为："<<endl;
	for( i=0;i<n;i++)
	{
	cout<<dist[i]<<"  ";
	}
}

void main()
{
	int n=5,v=0;	
	int c[5][5]={
		0,10,INF,30,100,
		INF,0,50,INF,INF,
		INF,INF,0,INF,10,
		INF,INF,20,0,60,
		INF,INF,INF,INF,0};
	int dist[]={0};	 
	Dijkstra(n,v,dist,c);
}