本文共 2499 字，大约阅读时间需要 8 分钟。
注意 区别于上一个Dijkstra的实现 这里利用 edge[0][j] 值 对 dist 赋值
核心算法:
//本例 默认 起始点为 0 void Dijkstra(Graph g){ int i, j; for (i = 0; i < g.vex_num; i++) { dist[i] = g.edge[0][i];// 关键 ， 0可以为任意顶点 path[i] = -1; known[i] = 0; } int min; int u, v; //算法核心 for (i = 0; i < g.vex_num - 1; i++) {//顶点数少一次 一定可以遍历所有顶点了 min = INFINITY; for (j = 0; j < g.vex_num; j++) { if (dist[j] < min && known[j] == 0) { u = j; min = dist[j]; } } known[u] = 1; for (v = 0; v < g.vex_num; v++){ if (g.edge[u][v] < INFINITY && dist[v] > dist[u] + g.edge[u][v] && known[v] == 0) { dist[v] = dist[u] + g.edge[u][v]; path[v] = u; } } } //打印 长度 for(i = 0; i < g.vex_num; i++ ){ printf("%5d",dist[i]); }} #include#include #define MAXVEX 100#define INFINITY 65535int path[MAXVEX];int known[MAXVEX];int dist[MAXVEX];typedef struct Graph { int vex[MAXVEX]; int edge[MAXVEX][MAXVEX]; int vex_num, edge_num;}Graph;void init_graph(Graph *g) // 重要： c 语言 值传递的特性 必须传递 指针 { int i, j; for (i = 0; i < g->vex_num; i++) { for (j = 0; j < g->vex_num; j++) { if (i == j) g->edge[i][j] = 0; else g->edge[i][j] = INFINITY; } }}void create_graph(Graph *g){ int i, j, k, w; scanf("%d%d",&g->vex_num,&g->edge_num); for (i = 0; i < g->vex_num; i++){ scanf("%d",&g->vex[i]); } init_graph(g); for (k = 0; k < g->edge_num; k++) { scanf("%d%d%d", &i, &j, &w); g->edge[i][j] = w; //g->edge[j][i] = w; //也可以是无向图 }}//本例 默认 起始点为 0 void Dijkstra(Graph g){ int i, j; for (i = 0; i < g.vex_num; i++) { dist[i] = g.edge[0][i];// 关键 ， 0可以为任意顶点 path[i] = -1; known[i] = 0; } int min; int u, v; //算法核心 for (i = 0; i < g.vex_num - 1; i++) {//顶点数少一次 一定可以遍历所有顶点了 min = INFINITY; for (j = 0; j < g.vex_num; j++) { if (dist[j] < min && known[j] == 0) { u = j; min = dist[j]; } } known[u] = 1; for (v = 0; v < g.vex_num; v++){ if (g.edge[u][v] < INFINITY && dist[v] > dist[u] + g.edge[u][v] && known[v] == 0) { dist[v] = dist[u] + g.edge[u][v]; path[v] = u; } } } //打印 长度 for(i = 0; i < g.vex_num; i++ ){ printf("%5d",dist[i]); }}void print_graph(Graph g){ int i, j; for (i = 0; i < g.vex_num; i++) { for (j = 0; j < g.vex_num; j++) { if(g.edge[i][j] == INFINITY) printf("%5s","*"); else printf("%5d",g.edge[i][j]); } printf("\n"); }}void print_path(Graph g, int end) { if(path[end] != -1){ print_path(g, path[end]); printf("->"); } printf("%d",g.vex[end]); } int main(){ Graph g; create_graph(&g); Dijkstra(g); //print_graph(g); return 0;}
转载地址：http://nximi.baihongyu.com/