dijkstrapath.cpp

数据结构算法

#include<stdio.h>
/////////////////////////////
int M=10000;
int min(int x,int y)
	{if(x>=y)
	     return(y);
     else
		 return(x);}
///////////////////////////////
void main()
{int cost[8][8]={{0,M,M,M,M,M,M,M},{300,0,M,M,M,M,M,M},
			{1000,800,0,M,M,M,M,M},{M,M,1200,0,M,M,M,M},
			{M,M,M,1500,0,250,M,M},{M,M,M,1000,M,0,900,1400},
			{M,M,M,M,M,M,0,1000},{1600,M,M,M,M,M,M,0}};
 int s[8],dist[8];
 int i,j,k,num,u;
 int v=4;
 for(i=0;i<8;i++)
 {
	 s[i]=0;
	 dist[i]=cost[v][i];
 }
 printf("the original matrix is:\n");
 for(i=0;i<8;i++)
 {
	 for(j=0;j<8;j++)
	 {
		 printf("%6d   ",cost[i][j]);
	 }
	 printf("\n");
 }
 s[v]=1;
 dist[v]=0;
 num=2;
 printf("*********************************************************************\n");
 while(num<8)
 {    
	 for(i=7;i>=0;i--)
	 {
		 if(s[i]==0)
		 {   
			 k=dist[i];
		 }
	 }
	 for(j=0;j<8;j++)
	 {
		 if(dist[j]<=k && s[j]==0)
		 {   
			 k=dist[j];
			 u=j;
		 }
	 }
     s[u]=1;
	 num=num+1;
	 for(i=0;i<8;i++)
	 {
		 if(s[i]==0)
		 {
			 dist[i]=min(dist[i],(dist[u]+cost[u][i]));
		 }
	 }
 }
 printf("the result is:\n");
 for(j=0;j<8;j++)
 {
	  printf("the shortest path from 5 to %d is %d \n",j+1,dist[j]);
 }

}