#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXEDgE 20#define MAXVEX 20#define INFINITY 65535typedef int Status;    /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */ typedef struct{    int vexs[MAXVEX];    int arc[MAXVEX][MAXVEX];    int numVertexes, numEdges;}Mgraph;typedef int Patharc[MAXVEX];            /* 用于存儲最短路徑下標的數組 */typedef int ShortPathTable[MAXVEX];        /* 用于存儲到各點最短路徑的權值和 */void CreateMgraph(Mgraph *g){    int i, j;    /* PRintf("請輸入邊數和頂點數:"); */    g->numEdges=16;    g->numVertexes=9;    for (i = 0; i < g->numVertexes; i++)/* 初始化圖 */    {        g->vexs[i]=i;    }    for (i = 0; i < g->numVertexes; i++)/* 初始化圖 */    {        for ( j = 0; j < g->numVertexes; j++)        {            if (i==j)                g->arc[i][j]=0;            else                g->arc[i][j] = g->arc[j][i] = INFINITY;        }    }    g->arc[0][1]=1;    g->arc[0][2]=5;     g->arc[1][2]=3;     g->arc[1][3]=7;     g->arc[1][4]=5;     g->arc[2][4]=1;     g->arc[2][5]=7;     g->arc[3][4]=2;     g->arc[3][6]=3;     g->arc[4][5]=3;    g->arc[4][6]=6;    g->arc[4][7]=9;     g->arc[5][7]=5;     g->arc[6][7]=2;     g->arc[6][8]=7;    g->arc[7][8]=4;    for(i = 0; i < g->numVertexes; i++)    {        for(j = i; j < g->numVertexes; j++)        {            g->arc[j][i] =g->arc[i][j];        }    }}/* Dijkstra算法，求有向網g的v0頂點到其余頂點v的最短路徑P[v]及帶權長度D[v] */ /* P[v]的值為前驅頂點下標,D[v]表示v0到v的最短路徑長度和 */ void ShortestPath_Dijkstra(Mgraph g, int v0, Patharc *P, ShortPathTable *D){     int v,w,k,min;     int final[MAXVEX];                    /* final[w]=1表示求得頂點v0至vw的最短路徑 */        /* 初始化數據 */    for(v=0; v<g.numVertexes; v++)            {         final[v] = 0;                    /* 全部頂點初始化為未知最短路徑狀態 */        (*D)[v] = g.arc[v0][v];            /* 將與v0點有連線的頂點加上權值 */        (*P)[v] = 0;                    /* 初始化路徑數組P為0 */     }    (*D)[v0] = 0;                        /* v0至v0路徑為0 */     final[v0] = 1;                        /* v0至v0不需要求路徑 */         /* 開始主循環，每次求得v0到某個v頂點的最短路徑 */     for(v=1; v<g.numVertexes; v++)     {        min=INFINITY;                    /* 當前所知離v0頂點的最近距離 */         for(w=0; w<g.numVertexes; w++) /* 尋找離v0最近的頂點 */         {             if(!final[w] && (*D)[w]<min)             {                 k=w;                 min = (*D)[w];            /* w頂點離v0頂點更近 */             }         }         final[k] = 1;                    /* 將目前找到的最近的頂點置為1 */        /* 修正當前最短路徑及距離 */        for(w=0; w<g.numVertexes; w++)         {            /* 如果經過v頂點的路徑比現在這條路徑的長度短的話 */            if(!final[w] && (min+g.arc[k][w]<(*D)[w]))             {                 /* 說明找到了更短的路徑，修改D[w]和P[w] */                (*D)[w] = min + g.arc[k][w]; /* 修改當前路徑長度 */                 (*P)[w]=k;             }         }     }}int main(void){     int i,j,v0;    Mgraph g;     Patharc P;     ShortPathTable D; /* 求某點到其余各點的最短路徑 */     v0=0;        CreateMgraph(&g);        ShortestPath_Dijkstra(g, v0, &P, &D);     printf("最短路徑倒序如下:/n");     for(i=1;i<g.numVertexes;++i)     {         printf("v%d - v%d : ",v0,i);        j=i;        while(P[j]!=0)        {            printf("%d ",P[j]);            j=P[j];        }        printf("/n");    }     printf("/n源點到各頂點的最短路徑長度為:/n");     for(i=1;i<g.numVertexes;++i)         printf("v%d - v%d : %d /n",g.vexs[0],g.vexs[i],D[i]);     return 0;}