²      问题描述

交通网络中常常提出这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最短？以上问题就是带权图中求最短路径的问题。

²      基本要求

⑴用Dijkstra算法求最短路径，图中的顶点数n不得少于10个。

⑵用户输入源点和目标点后，程序应输出源点到目标点的最短路径，并计算出途中所需时间或花费的交通费用。

源程序：

#include <stdio.h>
#include <stdlib.h>
#define INFINITY 32767
#define MaxVertexNum 30
typedef char VertexType;
typedef int EdgeType;
typedef struct{
   VertexType vexs[MaxVertexNum];
   EdgeType edges[MaxVertexNum][MaxVertexNum];
   int n,e;
}MGraph;

typedef enum{
   FALSE,TRUE
}Boolean;

void CreateMGraph(MGraph *G)
{
 int i,j,k,w;
 printf("\nEnter n & e:\n");
 scanf("%d%d",&G->n,&G->e);
 for (i=0;i<G->n;i++)
    for (j=0;j<G->n;j++)
       G->edges[i][j]=INFINITY;
 printf("Enter edge(i & j)& weight:\n");
 for (k=0;k<G->e;k++)
    {
     scanf("%d%d%d",&i,&j,&w);
     G->edges[i][j]=w;
    }
}
void Dijkstra(MGraph *G,long D[],int P[],int s)
{
 int i,j,k,min;
 Boolean S[MaxVertexNum];
 for(i=0;i<G->n;i++)
  {
   S[i]=FALSE;
   D[i]=G->edges[s][i];
   if(D[i]<INFINITY)
      P[i]=s;
   else
      P[i]=-1;
  }
 S[s]=TRUE;
 D[s]=0;
 for(i=0;i<G->n-1;i++)
  {
   min=INFINITY;
   for(j=0;j<G->n;j++)
      if(!S[j]&&D[j]<min)
        {
         min=D[j];
         k=j;
        }
   if(min==INFINITY)
      return;
   S[k]=TRUE;
   for(j=0;j<G->n;j++)
      if(!S[j]&&(D[j]>D[k]+G->edges[k][j]))
        {
         D[j]=D[k]+G->edges[k][j];
         P[j]=k;
        }
  }
}
void Print(MGraph *G,int P[],long D[],int t)
{
 int i=0,pre,a[MaxVertexNum];
 long k=32767;
 if(D[t]==k)
   {
    printf("no way!\n");
    return;
   }
 printf("Distance:%ld,Path:",D[t]);
 a[i]=t;
 pre=P[t];
 while(pre!=-1)
  {
   a[++i]=pre;
   pre=P[pre];
  }
 for(;i>=0;i--)
   printf("%d  ",a[i]);
}
void main()
{
 void CreateMGraph(MGraph *G);
 void Dijkstra(MGraph *G,long D[],int P[],int s);
 void Print(MGraph *G,int P[],long D[],int t);
 long int D[MaxVertexNum];
 int P[MaxVertexNum],s,t,l=1,k=1;
 MGraph *G;
 CreateMGraph(G);
 do
  {
   printf("\n*****please make a choice*****\n");
   printf("1.search\n0.EXIT\n");
   printf("******************************\n");
   scanf("%d",&l);
   switch(l)
    {
     case 0:k=0;break;
     case 1:
            if(l==1)
             {
              printf("shu ru yuan dian & zhong dian:\n");
              scanf("%d%d",&s,&t);
             }
            Dijkstra(G,D,P,s);
            Print(G,P,D,t);
            break;
    }
  }while(k);
}