source.c

单源点最短路径算法 * 本程序用来实现单源点最短路径（E.Dijkstra）算法 * 在Turbo C2.0编译器下编译通过 * 算法过程中 * 每条边的两个顶点和权值由用户输入

/**
 * @(#)source.c
 *
 *
 * @author ztssky
 * @version 1.00 2007/1/2
 * 说明如下：
 * 本程序用来实现单源点最短路径（E.Dijkstra）算法
 * 在Turbo C2.0编译器下编译通过
 * 算法过程中
 * 每条边的两个顶点和权值由用户输入，格式：1 2 20
 * 程序默认源点为第一个顶点
 * 算法完成后输出路径长度和路径上的顶点
 * 格式为：路径长度：目标顶点<-经过的顶点...<-源点
 */
#include<stdio.h>

#define N 7  /*顶点数*/
#define E 12  /*边数*/

#define INT_MAX 32767 /*边的权值不可能达到的值*/

void main()
{
	int arcs[N+1][N+1]; /*图的邻接矩阵*/
  int dist[N+1];  /*存放源点到各顶点的最短路径*/
  int path[N+1];  /*存放在最短路径上该顶点的前一顶点号*/
  int s[N+1];   /*已求得的在最短路径上的顶点的顶点号*/
  int i,j,w,k;
  int min,u,pre;
  for( i=1; i<=N;i++)/*初始化邻接矩阵*/
    for(j=1; j<=N; j++)
      if(i==j)arcs[i][j]=0;/*对角线上值为0*/
      else arcs[i][j]=INT_MAX;/*其他的值置为最大*/
  for(k=1; k<=E; k++)
  {
    scanf("%d %d %d",&i,&j,&w);/*输入第一个顶点、第二个顶点、边的权值*/
    arcs[i][j]=w;/*构造邻接矩阵*/
  }
  for(i=1; i<=N; i++)/*初始化成本和路径*/
  {
  	dist[i]=arcs[1][i];/*源点到各顶点的路径长度暂置为源点到该点的直接路径长度*/
    s[i]=0;
    if((i!=1)&&(dist[i]<INT_MAX))path[i]=1;
    else path[i]=0;/*路径置为空*/
  }
  s[1]=1; dist[1]=0;
  for(i=1;i<N;i++)/*主循环，E.Dijkstra算法*/
  {
    min=INT_MAX;u=1;
    for(j=1;j<=N;j++)
    if(!s[j]&&dist[j]<min){u=j,min=dist[j];}
    s[u]=1;
    for(w=1;w<=N;w++)
     if(!s[w]&&arcs[u][w]<INT_MAX&&dist[u]+arcs[u][w]<dist[w])
     	{dist[w]=dist[u]+arcs[u][w]; path[w]=u;}
  }
  for(i=1;i<=N;i++)/*输出算法的结果*/
  {
   if(i!=1)
   {
  	 printf("%d:",dist[i]);/*输出路径长度*/
  	 printf("%d",i);/*输出目标顶点*/
     pre=path[i];
     while(pre!=0)
     {
    	 printf("<-%d",pre);/*输出路径*/
       pre=path[pre];
     }
     printf("\n");
   }
  }
  getch();/*等待按键退出*/
}