看《數(shù)據(jù)結(jié)構(gòu)》的時候，發(fā)現(xiàn)教科書上提供的算法貌似只是把最短路徑上的頂點放到一個二維數(shù)組里頭就完事了，卻沒有給出路徑上頂點的輸出次序。一個頂點數(shù)組就叫做最短路徑，編者也太不負責任了吧，好歹也給個根據(jù)得到的路徑頂點數(shù)組求該路徑的方法吧？還是編者想讓讀者有自己思考的余地？？不過回頭想想，如果通過那個路徑頂點的二維數(shù)組，按照路徑長度從小到大，輸出長路徑時先輸出短路徑包含的頂點的原則來分別輸出這些路徑，應(yīng)該還是能搞定的（雖然沒試過……）。

        不過，自己還是重新寫了一個與教科書有點不同的Dijkstra算法出來，算法基本思想還是一樣的，只是這里的輔助變量有些區(qū)別而已，同時也給出了一個利用棧來求最短路徑中頂點的輸出次序。程序在VC++6.0編譯通過了，而算法的具體過程如下：

#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char VertexType;//頂點類型
#define INFINITY 2147483647//表示兩頂點不相連的權(quán)值為2147483647
#define MAX_VERTEX_NUM 20//表示圖中最大頂點數(shù)
#define MAX_STACK_NUM MAX_VERTEX_NUM

typedef struct Stack{
int vertex[MAX_STACK_NUM];
int top;
}Stack;

//棧初始化
Status InitStack(Stack *s){
int i;
for(i=0;i   s->vertex[i]=0;
s->top=-1;
return OK;
}

//入棧
Status Push(Stack *s,int v){
if(s->top==MAX_STACK_NUM-1){
   printf('棧滿，無法入棧！\n');
   return ERROR;
}
s->vertex[++s->top]=v;
return OK;
}

//退棧
Status Pop(Stack *s,int *e){
if(s->top==-1){
   printf('空棧無法彈出！\n');
   return ERROR;
}
*e=s->vertex[s->top--];
return OK;
}

//判斷棧是否為空
Status StackEmpty(Stack s){
if(s.top==-1)
   return TRUE;
return FALSE;
}

typedef struct MGraph{
VertexType vexs[MAX_VERTEX_NUM];//頂點數(shù)組
int adj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//圖的鄰接矩陣
int vexnum,arcnum;
}MGraph;

//頂點定位，不存在則返回-1
int LocateVex(MGraph G,VertexType v){
int i;
for(i=0;i   if(G.vexs[i]==v)
    return i;
   return -1;
}

//建立無向圖鄰接矩陣
Status CreateGraph(MGraph *G){
VertexType v1,v2;
int i,j,k;

printf('構(gòu)造有向圖\n\n');
printf('請輸入頂點個數(shù)：');
scanf('%d',&G->vexnum);
if(G->vexnum>MAX_VERTEX_NUM) return ERROR;
printf('輸入邊數(shù)：');
scanf('%d',&G->arcnum);
if(G->arcnum>MAX_VERTEX_NUM*(MAX_VERTEX_NUM-1)/2) return ERROR;//邊輸入有誤
printf('\n');

for(i=0;ivexnum;++i){
   getchar();
   printf('輸入第%d個頂點：',i+1);
   scanf('%c',&G->vexs[i]);
}

for(i=0;ivexnum;++i)
   for(j=0;jvexnum;++j)
    G->adj[i][j]=INFINITY;//鄰接矩陣初始化
   printf('\n');
  
   for(k=0;karcnum;++k){
    getchar();
    printf('輸入第%d條邊對應(yīng)的起點和終點：',k+1);
    scanf('%c%c',&v1,&v2);
    i=LocateVex(*G,v1);
    j=LocateVex(*G,v2);
    printf('輸入該邊的權(quán)值：');
    scanf('%d',&G->adj[i][j]);
   }
   return OK;
}

//返回v的第一個鄰接點位置，不存在則返回-1
int FirstAdjVex(MGraph G,int v){
int j;
for(j=0;j   if(G.adj[v][j]==1)
    return j;
   return -1;
}

//返回v相對于w的下一個鄰接點，沒有則返回-1
int NextAdjVex(MGraph G,int v,int w){
int k;
for(k=w+1;k   if(G.adj[v][k]==1)
    return k;
   return -1;
}

//打印鄰接矩陣
void Print_Graph_Array(MGraph g){
int i,j;
printf('\n圖鄰接矩陣是：\n ');
for(i=0;i   printf(' %c',g.vexs[i]);
for(i=0;i   printf('\n%c ',g.vexs[i]);
   for(j=0;j    if(g.adj[i][j]==INFINITY)
     printf('%d ',g.adj[i][j]-INFINITY);
    else
     printf('%d ',g.adj[i][j]);
   }
}
printf('\n\n');
}

//Dijkstra算法
void ShortestPath_Dij(MGraph g,int v0,int D[],int P[]){
//D[]存放到達各個頂點的最小權(quán)值之和
//路徑數(shù)組P[]用于求各個頂點最短路徑中頂點的先后次序，如果P[i]不等于i，則表示在最短路徑中到達點vi前必須先到達點v(P[i])

int i,j;
int location_min,min;//location_min存放每一次“路徑試探”時找到的最小權(quán)值min對應(yīng)的頂點的下標
int final[MAX_VERTEX_NUM];//數(shù)組final[i]為true當且僅當vi已經(jīng)找到從v0出發(fā)的最短路徑

for(j=0;j   D[j]=g.adj[v0][j];//數(shù)組D[]初始化
   final[j]=FALSE;//數(shù)組final[]初始化
  
   //數(shù)組P[]初始化
   if(g.adj[v0][j]!=INFINITY)
    P[j]=j;
   else
    P[j]=INFINITY;
}
final[v0]=TRUE;

for(i=1;i   min=INFINITY;

   //求每一次“路徑試探”時最小權(quán)值對應(yīng)的頂點的下標，并保存到location_min中
   for(j=0;j    if(final[j]) continue;
    if(D[j]     min=D[j];
     location_min=j;
    }
   }
   final[location_min]=TRUE;
  
   //試探vertex[location_min]到其余的某個頂點vertex[j]的權(quán)值與D[location_min]之和是否小于D[j]
   for(j=0;j    if(final[j]) continue;
    if(g.adj[location_min][j]!=INFINITY && D[location_min]+g.adj[location_min][j]     D[j]=D[location_min]+g.adj[location_min][j];
     P[j]=location_min;
    }
   }
} 
}

//根據(jù)求得的路徑數(shù)組P[]依次打印各條最短路徑的線路及其最小權(quán)值和
void Print_ShortestPaths(MGraph g,int v0,int D[],int P[],int vertexnum){
int i,j;
int e;
Stack s;

for(i=0;i   if(i==v0) continue;

   printf('%c到%c的最短路徑是：',g.vexs[v0],g.vexs[i]);
   if(P[i]==INFINITY) 
    printf('無\n\n');
   else{
    j=i;
    InitStack(&s);
    Push(&s,j);
    while(g.vexs[j]!=g.vexs[P[j]]){
     Push(&s,P[j]);
     j=P[j];
    }//如果g.vexs[j]與g.vexs[P[j]]不相等，則表示在最短路徑中輸出頂點g.vexs[j]前要先輸出頂點g.vexs[p[j]]
    Push(&s,v0);
    while(!StackEmpty(s)){
     Pop(&s,&e);
     printf('%c ',g.vexs[e]);
    }
    printf('\n該路徑的總權(quán)值為：%d\n\n',D[i]);
   }//從路徑的終點到起點依次進棧，最后通過棧將路徑的各頂點輸出
}
}

void main(){
MGraph g;
char quit;
VertexType startpoint;
int v0;
int D[MAX_VERTEX_NUM],P[MAX_VERTEX_NUM];
Stack s;

do {
   if(!CreateGraph(&g)){
    printf('輸入錯誤！\n');
    goto ErrMrk;
   }
  
   Print_Graph_Array(g);

   printf('輸入路徑起點：');
   getchar();
   startpoint=getchar();
   printf('\n');
   v0=LocateVex(g,startpoint);
   ShortestPath_Dij(g,v0,D,P);//求起點到各個頂點的最短路徑
   Print_ShortestPaths(g,v0,D,P,g.vexnum);//打印各條最短路徑及相應(yīng)的總權(quán)值
  
   printf('\n\n');

ErrMrk: printf('退出請按0，重新測試請按任意鍵：');
   getchar();
   quit=getchar();
   system('cls');
} while(quit!='0');
}