有向图

#include <stdio.h>
#define N 20
#define TRUE 1
#define INF 32766
#define INFIN 32767

typedef struct {
	int vexnum, arcnum;
	char vexs[N];
	int arcs[N][N];
} graph;

void createGraph_w(graph *g, int flag);
void dijkstra(graph g, int v);
void printPath(graph g, int startVex, int endVex, int path[]);

// 创建带权有向图的邻接矩阵
void createGraph_w(graph *g, int flag) {
	char s;
	int i = 0, j, t, w, num = 0;
	for (int a = 0; a < N; a++)
		for (int b = 0; b < N; b++)
			g->arcs[a][b] = INFIN;
	for (int c = 0; c < N; c++)
		g->arcs[c][c] = 0;
	s = getchar();
	while (s != '#') {
		g->vexs[i] = s;
		i++;
		s = getchar();
	}
	getchar();
	g->vexnum = i;
	scanf("%d,%d,%d", &j, &t, &w);
	while (j != -1 && t != -1 && w != -1) {
		g->arcs[j][t] = w;
		num++;
		scanf("%d,%d,%d", &j, &t, &w);
	}
	g->arcnum = num;
}

// 根据 Dijkstra 算法计算出的最短路径，输出最短路径
void printPath(graph g, int startVex, int EndVex, int path[]) {
	if (startVex == EndVex) {
		printf("%c", g.vexs[startVex]);
		return;
	}

	if (path[EndVex] == -1) {
		printf("no path from %c to %c", g.vexs[startVex], g.vexs[EndVex]);
		return;
	}

	printPath(g, startVex, path[EndVex], path);
	printf("-->%c", g.vexs[EndVex]);
}

// Dijkstra 算法求单源最短路径
void dijkstra(graph g, int v) {
	int i, j, k;
	int dist[N];
	int path[N];
	int visited[N];

	for (i = 0; i < g.vexnum; i++) {
		dist[i] = g.arcs[v][i];
		visited[i] = 0	;

		if (dist[i] < INF && dist[i] > 0) {
			path[i] = v;
		} else {
			path[i] = -1;
		}
	}

	visited[v] = TRUE;
	dist[v] = 0;

	for (i = 1; i < g.vexnum; i++) {
		int min = INF;

		for (j = 0; j < g.vexnum; j++) {
			if (!visited[j] && dist[j] < min) {
				min = dist[j];
				k = j;
			}
		}

		visited[k] = TRUE;

		for (j = 0; j < g.vexnum; j++) {
			if (!visited[j] && g.arcs[k][j] < INF) {
				int newdist = dist[k] + g.arcs[k][j];

				if (newdist < dist[j]) {
					dist[j] = newdist;
					path[j] = k;
				}
			}
		}
	}

	for (i = 0; i < g.vexnum; i++) {
		if (i != v) {
			printf("%c->%c:", g.vexs[v], g.vexs[i]);
			printPath(g, v, i, path);
			printf("\n");
		}
	}
}

int main() {
	graph g;
	int k;
	createGraph_w(&g, 0);
	scanf("%d", &k);
	dijkstra(g, k);
	return 0;
}