#include<stdio.h>
#define INFINITY 10000 #define MaxVertexNum 100 #define FALSE 0 #define TRUE 1
typedef char Vertex_Type; typedef char Path_Matrix; typedef int Short_Path_Table; typedef int Edge_Type;
typedef struct{ Vertex_Type vexs[MaxVertexNum]; Edge_Type edges[MaxVertexNum][MaxVertexNum]; int n,e;}MGraph;
void ShortestPath(MGraph *G,int v0,Path_Matrix P[],Short_Path_Table D[]) {int v,i,min,pre,w,final[MaxVertexNum]; for(v=0;v<G->n;++v) {final[v]=FALSE;D[v]=G->edges[v0][v]; P[v0]=-1; if(D[v]<INFINITY&&v!=v0)P[v]=v0; if(D[v]==INFINITY) P[v]=-2;} D[v0]=0;final[v0]=TRUE; for(i=1;i<G->n;++i) {min=INFINITY; for(w=0;w<G->n;++w) if(!final[w]) if(D[w]<min){v=w;min=D[w];} final[v]=TRUE; for(w=0;w<G->n;++w) if(!final[w]&&(min+G->edges[v][w])<D[w]) {D[w]=min+G->edges[v][w]; P[w]=v;} } for(i=1;i<G->n;i++) {if(P[i]==-2) printf("max %d\n",i); else {printf("%d v%i",D[i],i); pre=P[i]; while(pre>0) {printf("<-%s",G->vexs[pre]);pre=P[pre];} printf("<-v0\n");} }}
main() {MGraph *G; Path_Matrix P[MaxVertexNum]; Short_Path_Table D[MaxVertexNum]; int v0=0,i,j,k,w; clrscr(); G=(MGraph *)malloc(sizeof(MGraph)); printf("Input totals of Vertexs and Edges(e.g:Vertex_Totals,Edge_Totals):\n");/*对图的初始化，给图的顶点数和边数赋值*/ scanf("%d,%d",&G->n,&G->e); printf("Input information for Vertexs(e.g:Vertex_SN<CR>):\n");/*给图的每个顶点输入一个序列号*/ for(i=0;i<G->n;i++) scanf("%s",G->vexs[i]); for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) G->edges[i][j]=INFINITY;/*设定一个最大值给每条边，让每个顶点初始化的时候相当于权值无穷大即互不相连*/ printf("Input every edge together two Vertexs' SN(e.g:i,j):\n"); for(k=0;k<G->e;k++) /*输入要进行赋值的边所确定的两个顶点*/ {scanf("%d,%d",&i,&j); printf("weight of the edge<v%d,v%d>:",i,j);/*给固定的边赋值*/ scanf("%d",&G->edges[i][j]);} ShortestPath(G,v0,P,D);/*Dijkstra算法的注释书上有，我就不赘述了*/ getch();}
其实这个程序并没有什么难点，算法给定，剩下的都是参数传入的匹配。
[此贴子已经被作者于2005-5-14 0:13:37编辑过]
