void init_graph( Graph g, int start){	int i;	for (i = 0; i < g.vex_num; i++) {	//	dist[i] = get_weight(g, start, i);//如果最开始 就获取起始点的临节点  										path[i] = BEGIN;					//需要改变相应临节点的path 值  		known[i] = FALSE;		dist[i] = INFINITY;	}	dist[start] = 0;	//known[start] = TRUE;}int find_min(Graph g){	int i;	int index;	int min;	min = INFINITY;//每次初始为INFINITY 	for (i = 0; i < g.vex_num; i++) {		if(dist[i] < min && known[i] == FALSE){			min = dist[i];			index = i;		}	}	if (min == INFINITY)		return NOTEXIST;	else{		return index;	}}void Dijkstra(Graph g)  //O（V^2）{	ENode *p;	int v;	while(1){		v = find_min(g);//每次 找到 未known的 dist 最小的 顶点 v 索引		if(v == NOTEXIST)			break;		known[v] = TRUE;//访问了		p = g.vex[v].first_edge;		while(p != NULL){//遍历v 的每个临接点 			if(known[p->ivex] == FALSE){				if(dist[v] + p->weight < dist[p->ivex]){//出现到p->ivex新路径时 若更短则更新					dist[p->ivex] = dist[v] + p->weight;					path[p->ivex] = v;				}			}			p = p->next_edge;		}		 	}}

#include
    
     #include
     
      #include
      
       #define INFINITY 65535#define BEGIN -1  #define MAXVEX 100#define NOTEXIST -1#define TRUE 1#define FALSE 0int path[MAXVEX];int dist[MAXVEX];int known[MAXVEX];typedef char VertexType;typedef int WeightType;typedef struct ENode {	int ivex;//顶点 索引  	WeightType weight;	struct ENode* next_edge;}ENode;typedef struct VNode {	VertexType data; // 顶点 信息  	ENode* first_edge;}VNode;typedef struct Graph {	VNode vex[MAXVEX];	int vex_num, edge_num;}Graph;char read_char(){	char ch;	do {		ch = getchar();	} while (!isalpha(ch));	return ch;}int get_pos(Graph g, char ch){	int i;	for (i = 0; i < g.vex_num; i++) {		if (ch == g.vex[i].data)			return i;	}	return -1;}void link_last(ENode* list, ENode *last){	ENode* p;	p = list;	while (p->next_edge != NULL) {		p = p->next_edge;	}	p->next_edge = last;}void create_graph(Graph *g){	int i, w;	printf("请输入顶点数和边数:\n");	scanf("%d%d", &g->vex_num, &g->edge_num);	printf("请输入顶点信息:\n");	for (i = 0; i < g->vex_num; i++) {		g->vex[i].first_edge = NULL;		g->vex[i].data = read_char();	}	printf("请输入边 :\n");	for (i = 0; i < g->edge_num; i++) {		int p1, p2;		char c1, c2;		c1 = read_char();		c2 = read_char();		scanf("%d", &w);		p1 = get_pos(*g, c1);		p2 = get_pos(*g, c2);		ENode* node1;		node1 = (ENode*)malloc(sizeof(ENode));		if (node1 == NULL) {			printf("error");			return;		}		node1->next_edge = NULL;		node1->ivex = p2;		node1->weight = w;		if (g->vex[p1].first_edge == NULL)			g->vex[p1].first_edge = node1;		else			link_last(g->vex[p1].first_edge, node1);	}}int get_weight(Graph g, int start, int end)	{		ENode* node;		if(start == end){			return 0;		}			node = g.vex[start].first_edge;		while(node != NULL){			if(end == node->ivex){				return node->weight;			}			node = node->next_edge;		}		return INFINITY;	} void print_graph(Graph g){	int i;	ENode* p;	for (i = 0; i < g.vex_num; i++) {		printf("%c", g.vex[i].data);		p = g.vex[i].first_edge;		while (p != NULL) {			printf("(%c, %c)->w =%d ", g.vex[i].data, g.vex[p->ivex].data, p->weight);			p = p->next_edge;		}		printf("\n");	}}void init_graph( Graph g, int start){	int i;	for (i = 0; i < g.vex_num; i++) {	//	dist[i] = get_weight(g, start, i);//如果最开始 就获取起始点的临节点  										path[i] = BEGIN;					//需要改变相应临节点的path 值  		known[i] = FALSE;		dist[i] = INFINITY;	}	dist[start] = 0;	//known[start] = TRUE;}int find_min(Graph g){	int i;	int index;	int min;	min = INFINITY;//每次初始为INFINITY 	for (i = 0; i < g.vex_num; i++) {		if(dist[i] < min && known[i] == FALSE){			min = dist[i];			index = i;		}	}	if (min == INFINITY)		return NOTEXIST;	else{		return index;	}}void Dijkstra(Graph g){	ENode *p;	int v;	while(1){		v = find_min(g);		if(v == NOTEXIST)			break;		known[v] = TRUE;		p = g.vex[v].first_edge;		while(p != NULL){			if(known[p->ivex] == FALSE){				if(dist[v] + p->weight < dist[p->ivex]){					dist[p->ivex] = dist[v] + p->weight;					path[p->ivex] = v;				}			}			p = p->next_edge;		}		 	}}void print_path2(Graph g, int end)//这里 直接传递最后位置的索引 类比树 的后续遍历{	if (path[end] != BEGIN) {		print_path2(g, path[end]);		printf("->"); 	}	printf("%c ", g.vex[end].data);}int main(){	Graph g;	int start, end;	char ch1, ch2;	create_graph(&g);	printf("请输入起始点与终点:\n");	ch1 = read_char();	ch2 = read_char();	start = get_pos(g, ch1);	end = get_pos(g, ch2);	init_graph(g, start);		Dijkstra(g);		if(dist[end] == INFINITY)		printf("\n该两点间无路径.");	else{		printf("最短路径为:\n\n");		print_path2(g, end);		printf("\n\n最小花费 : %d",dist[end]);	}		getchar();	getchar();	return 0;}