9-10.c

这个是数据结构经典实现算法

#include "stdio.h"
#include <stdlib.h>
#define MaxVertexNum 100
typedef enum{FALSE,TRUE}Boolean;/*FALSE为0,tRUE为1*/
Boolean visited[MaxVertexNum];
typedef int Vertextype;
typedef struct node{/*边表结点*/
	int adjvex; /*邻接点域*/
	struct node *next; /*链域*/
	/*若要表示边上的权,则应增加一个数据域*/
}EdgeNode;
typedef struct vnode{ /*顶点表结点*/
	Vertextype vertex; /*顶点域*/
	EdgeNode *firstedge;/*边表头指针*/
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];/*AdjList是邻接表类型*/
typedef struct ALGraph{
	AdjList adjlist;/*邻接表*/
	int n,e; /*图中当前顶点数和边数 */
}Graphic; /*对于简单的应用,无须定义此类型,可直接使用AdjList类型。*/
int D[MaxVertexNum];
void CreateGraphic(Graphic *G)
{/*建立无向图的邻接表表示*/
     	int i,j,k;
      	EdgeNode *s;
      	scanf("%d%d",&G->n,&G->e); /*读人顶点数和边数*/
      	for(i=0;i<G->n;i++){/*建立顶点表*/
        	G->adjlist[i].vertex=getchar(); /*读入顶点信息*/
        	G->adjlist[i].firstedge=NULL;/*边表置为空表*/
       	}
      	for(k=0;k<G->e;k++){/*建立边表*/
         	scanf("%d%d",&i,&j);/*读入边(vi,vj)的顶点对序号*/
         	s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成边表结点*/
         	s->adjvex=j; /*邻接点序号为j*/
         	s->next=G->adjlist[i].firstedge;
 	        G->adjlist[i].firstedge=s; /*将新结点*s插入顶点vi的边表头部*/
         	s=(EdgeNode *)malloc(sizeof(EdgeNode));
         	s->adjvex=i; /*邻接点序号为i*/
         	s->next=G->adjlist[j].firstedge;
         	G->adjlist[j].firstedge=s; /*将新结点*s插入顶点vj的边表头部*/
        }   
} 

void Dijkstra(Graphic *G,int D[],Vertextypes){
    	/*用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度*/
   		/*以下是初始化操作*/
		int i,j;
      	//S={s};D[s]=0; /*设置初始的红点集及最短距离*/
      	for(/*all i∈ V-S*/ ) /*对蓝点集中每个顶点i*/
          	//D[i]=G[s][i]; /*设置i初始的估计距离为w<s,i>*/
       	/*以下是扩充红点集*/
      	for(i=0;i<MaxVertexNum-1;i++)do{/*最多扩充n-1个蓝点到红点集*/
           	//D[k]=min{D[i]：all i V-S}; /*在当前蓝点集中选估计距离最小的顶点k*/
           	//if(D[k]等于∞)
                return; /*蓝点集中所有蓝点的估计距离均为∞时,*/
                     /*表示这些顶点的最短路径不存在。*/
           	//S=S∪{k}; /*将蓝点k涂红后扩充到红点集*/
           	for(/* all j∈V-S*/ )/*调整剩余蓝点的估计距离*/
               	if(D[j]>D[k]+G[k][j])
                /*新红点k使原D[j]值变小时,用新路径的长度修改D[j],*/
				/*使j离s更近。*/
   	            //D[j]=D[k]+G[k][j];
		}
}

void main(void)
{
	Graphic graph;
	Vertextype r=3;
	CreateGraphic(&graph);
	Dijkstra(&graph,D,r);
}