danyuan.txt

单源最短路径问题的动态规划算法,请大家多多指教

// 单源最短路径.cpp : Defines the entry point for the console application.
//

//#include <stdafx.h>
#include <iostream>
#define true 1
#define false 0
#define maxint 4294967295
using namespace std;

void Dijkstra(int n,int v,int *dist,int *prev,int **c)
{// int maxint=7;
  int i,j,temp,u;
  bool *s=new bool[n];
 for(i=1;i<=n;i++){
 	dist[i]=c[v][i];
	s[i]=false;
	if(dist[i]==maxint) prev[i]=0;
	else prev[i]=v;
}
dist[v]=0;s[v]=true;
for(i=1;i<n;i++){
	 temp=maxint;
	 u=v;
	for(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]<maxint)){
				int newdist=dist[u]+c[u][j];
				if(newdist<dist[j]){
					dist[j]=newdist;
					prev[j]=u;
				}
			}
}
}

int main()
{ int n,v,i,j;
  cout<<"Input n";
  cin>>n;
  cout<<endl;
  cout<<"输入初始源点：";
  cin>>v;
  cout<<endl;
  int *dist=new int[n];
  int *prev=new int[n];
  int *c=new int[(n)*(n)];
  cout<<"输入各边的权：";
  for(i=0;i<n;i++)
	  for(j=0;j<n;j++)
		  cin>>c[i][j];


  Dijkstra(n,v,dist,prev,&c);
	return 0;
}