資料結構：使用者輸入有向帶權圖，求從頂點到其他各頂點的最短路徑

最短路徑

對於使用者隨機輸入的一個有向帶權圖，求從某個頂點到其他各頂點的最短路徑

#include<stdio.h>
#define MAXV 20
#define INF 32              //若<vi,vj>不存在，則設<vi,vj>的權為32，表示無窮大
typedef struct
{      int no;              /*頂點編號*/
       //  InfoType info;   /*頂點其他資訊，此處省略*/
} VertexType;               /*頂點型別*/
typedef struct
{      int edges[MAXV][MAXV];       /*鄰接矩陣*/
       int n,e;                     /*頂點數,邊數*/
       VertexType vexs[MAXV];       /*存放頂點資訊*/
}MatGraph;                          /*完整的圖鄰接矩陣型別*/

void Dispath(MatGraph g,int dist[],int path[],int s[],int v)
{  int i,j,k;
   int apath[MAXV],d;
   printf("\n");
   for(i=0;i<g.n;i++)
     if(s[i]==1 && i!=v)
     {  printf("從頂點%d到頂點%d的路徑長度為：%d\t路徑為：",v,i,dist[i]);
        d=0;apath[d]=i;
        k=path[i];
        if(k==-1)
          printf("無路徑\n");
        else
        {  while(k!=v)
        {  d++;apath[d]=k;
           k=path[k];
        }
        d++;apath[d]=v;
        printf("%d",apath[d]);
        for(j=d-1;j>=0;j--)
           printf(",%d",apath[j]);
        printf("\n");
        }
     }
}

void Dijkstra(MatGraph g,int v)
{  int dist[MAXV],path[MAXV];
   int s[MAXV];
   int mindis,i,j,u;
   for (i=0;i<g.n;i++)
   {  dist[i]=g.edges[v][i];    //距離初始化
      s[i]=0;                   //s[]置空
      if(g.edges[v][i]<INF)      //路徑初始化
        path[i]=v;              //頂點v到i有邊時，置頂點i的前一個頂點為v
      else
        path[i]=-1;             //頂點v到i沒邊時，置頂點i的前一個頂點為-1
   }
   s[v]=1;path[v]=0;            //源點編號v放入s中
   for(i=0;i<g.n-1;i++)          //迴圈直到所有頂點的最短路徑都求出
   {  mindis=INF;               //mindis置最小長度初值
      for(j=0;j<g.n;j++)        //選取不在s中且具有最小距離的頂點u
         if(s[j]==0 && dist[j]<mindis)
         {  u=j;
            mindis=dist[j];
         }
      s[u]=1;                   //頂點u加入s中
      for(j=0;j<g.n;j++)     //修改不在s中的頂點的距離
         if(s[j]==0)
            if(g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
            {  dist[j]=dist[u]+g.edges[u][j];
               path[j]=u;
            }
   }
   Dispath(g,dist,path,s,v);    //輸出最短路徑
}

void main()
{  MatGraph G;
   int V,i,j;
   printf("請輸入圖G的頂點數和邊數(用逗號分隔)：");
   scanf("%d,%d",&G.n,&G.e);
   getchar();
   printf("請輸入圖G的頂點編號(用空格分隔)：");
   for(i=0;i<G.n;i++)
     scanf("%d",&G.vexs[i].no);
   getchar();
   printf("請分行輸入圖G的鄰接矩陣(同一行的元素用空格分隔，每輸入完一行按回車結束)：\n");
   for(i=0;i<G.n;i++)
   {  for(j=0;j<G.n;j++)
        scanf("%d",&G.edges[i][j]);
      getchar();
   }
   printf("請輸入源點V的編號：");
   scanf("%d",&V);
   Dijkstra(G,V);
}

執行結果

請輸入圖G的頂點數和邊數(用逗號分隔)：5,8
請輸入圖G的頂點編號(用空格分隔)：0 1 2 3 4
請分行輸入圖G的鄰接矩陣(同一行的元素用空格分隔，每輸入完一行按回車結束)：
0 1 0 1 1
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
1 0 1 1 0
請輸入源點V的編號：0

從頂點0到頂點1的路徑長度為：1 路徑為：0,1
從頂點0到頂點2的路徑長度為：0 路徑為：0,2
從頂點0到頂點3的路徑長度為：1 路徑為：0,3
從頂點0到頂點4的路徑長度為：1 路徑為：0,4