dijkstra.cpp

实现Dijkstra算法

//#include "stdafx.h"
#include "stdio.h"

#define INFINITE 100  //Define the infinite is 100

//Print the path from source point to point i(0 indicates point 1)
void printPath(int i, int path[])
{	 
	while (i!=0) { 
		printf("%d<--",i+1); 
		i=path[i]; 
	} 
	printf("%d\n",1); 
}

int main() 
{ 
	int j,i,n,k,t,**w,*s,*p,*d; 

	//Get the number of points
	printf("input the value of n:\n"); 
	scanf("%d",&n); 


	d = new int[n]; //Distance
	s = new int[n]; //point set
	p = new int[n]; //Path
	w = new int*[n]; //Weight

	for(i = 0; i < n; i++) { 
		w[i] = new int[n]; 
	} 

	//Get the weight from the user
	for(i = 0; i < n; i++) 
		for(j = 0; j < n; j++) 
			scanf("%d",&w[i][j]); 


	//Initial the path array
	for(s[0] = 1,i = 1; i < n; i++) { 
		s[i] = 0; 
		d[i] = w[0][i]; 
		if(d[i] < INFINITE) 
			p[i]=0; 
		else 
			p[i]=-1; 
	} 



	for(i = 1; i < n; i++) { 
		t = INFINITE; 
		k = 1; 
		for(j = 1; j < n; j++) 
			if((!s[j]) && (d[j] < t)) { 
				t = d[j]; 
				k = j; 
			} 
		s[k]=1;//point k join the S 
		for (j = 1; j < n; j++) 
			if((!s[j]) && (d[j] > d[k] + w[k][j])) { 
				d[j] = d[k] + w[k][j]; 
				p[j] = k; 
			} 

	} 


	//Print all the pathes from the source and distances
	printf("\n--------------------");
	for(int i=1; i<n; i++) {
		printf("Path from v1 to v%d:\n", i+1);
		printPath(i,p);
		printf("Distance:%d\n--------------------\n", d[i]);
	}
	
	return 0;

}