单源最短路径1.cpp

在学习计算算法分析与设计时编写的几个算法代码

#include"stdio.h"
#define MAX 1000
void Dijkstra(int n,int v,int dist[],int prev[],int c[][6])
{
	bool s[MAX];
	for(int i=1;i<=n;i++)
	{
		dist[i]=c[v][i];
		s[i]=false;
		if(dist[i]==MAX)prev[i]=0;
		else prev[i]=v;
	}
	dist[v]=0;s[v]=true;
	for(i=1;i<n;i++)
	{
		int temp=MAX;
		int u=v;
		for(int j=1;j<=n;j++)
			if((!s[j])&&(dist[j]<temp))
			{
				u=j;
				temp=dist[j];
			}
			s[u]=true;
			for(j=1;j<=n;j++)
				if((!s[j])&&(c[u][j]<MAX))
				{
					int newdist=dist[u]+c[u][j];
					if(newdist<dist[j])
					{
						dist[j]=newdist;
						prev[j]=u;
					}
				}
	}
}
main()
{
	int n=5;
	int v=1;
	int dist[6]={0};
	int prev[6]={0};
	int c[6][6]={{0},{0,0,10,MAX,30,100},{0,10,0,50,MAX,MAX},{0,MAX,50,0,20,10},{0,30,MAX,20,0,60},{0,100,MAX,10,60,0}};
    Dijkstra(n,v,dist,prev,c);
	for(int i=1;i<=n;i++)
		printf("%5d",dist[i]);
	printf("\n");
}