文章目录
算法完整代码
示例图代码结果
本文对应书《数据结构（C语言版）》严蔚敏》p188 讲述的源点到其余各点间的最短路径，而不是迪杰斯特拉算法或弗罗伊德算法。本文仅仅通过广度优先搜索结合书上原理写出最短路径算法
上面两种算法，请看主页下一篇博客，或者
算法
void ShortestPath(pGraph graph) { // 最短路径数组 int path[graph->vexnum]; bool visit[graph->vexnum]; for (int i=0; ivexnum; i++) { visit[i] = path[i] = 0; } // wfs 队列 pQueue q = CreateQueue(); EnQueue(q, graph->data[0]); visit[0] = true; while (!Empty(q)) { // 队列不为空就一直 wfs VNode p = DeQueue(q); // 取出一个顶点 // 将未访问连通点添加到队列 ArcNode *arc = p.firstArc; while (arc!=NULL) { // 将未访问顶点入队列 if (visit[arc->adj]==false) { EnQueue(q, graph->data[arc->adj]); } // 判断到该顶点的权值 if (path[arc->adj]==0 || path[arc->adj] > path[p.index] + arc->weight) { // 如果没有路径，添加路径 path[arc->adj] = path[p.index] + arc->weight; } arc = arc->nextArc; } } // 输出结果 for (int i=0; ivexnum; i++) { printf("%ct", graph->data[i].val); } printf("n"); for (int i=0; ivexnum; i++) { printf("%dt", path[i]); } printf("n");}
完整代码 示例图
代码
# include # include # include # define true 1 # define false 0# define MAX_SIZE 20typedef int bool;typedef char ElemType;// 图的邻接表typedef struct ArcNode { int adj; int weight; // 权 struct ArcNode *nextArc;} ArcNode;typedef struct { ElemType val; int index; ArcNode *firstArc;} VNode, AdjList[MAX_SIZE];typedef struct { AdjList data; int vexnum;} Graph, *pGraph;// 队列，wfstypedef struct { AdjList data; int start, end;} Queue, *pQueue;// 图pGraph CreateGraph();void AddVex(pGraph graph, ElemType vex);void AddArc(pGraph graph, ElemType vexa, ElemType vexb, int weight);// 队列pQueue CreateQueue();void EnQueue(pQueue q, VNode node);VNode DeQueue(pQueue q);bool Empty(pQueue q);// wfsvoid ShortestPath(pGraph graph);int main() { // 创建图 pGraph graph = CreateGraph(); // 添加顶点 AddVex(graph, 'a'); AddVex(graph, 'b'); AddVex(graph, 'c'); AddVex(graph, 'd'); AddVex(graph, 'e'); AddVex(graph, 'f'); // 添加边 AddArc(graph, 'a', 'c', 10); AddArc(graph, 'a', 'e', 30); AddArc(graph, 'a', 'f', 100); AddArc(graph, 'b', 'c', 5); AddArc(graph, 'c', 'd', 50); AddArc(graph, 'd', 'f', 10); AddArc(graph, 'e', 'd', 20); AddArc(graph, 'e', 'f', 60); // 最短路径 ShortestPath(graph); return 0;}pGraph CreateGraph() { pGraph graph = (pGraph) malloc(sizeof(Graph)); memset(graph, 0, sizeof(Graph)); return graph;}void AddVex(pGraph graph, ElemType vex) { graph->data[graph->vexnum].index = graph->vexnum; graph->data[graph->vexnum++].val = vex;}void AddArc(pGraph graph, ElemType vexa, ElemType vexb, int weight) { int index_a, index_b; for (int i=0; ivexnum; i++) { if (graph->data[i].val == vexa) { index_a = i; } if (graph->data[i].val == vexb) { index_b = i; } } // a 到 b ArcNode *arc_a = (ArcNode *) malloc(sizeof(ArcNode)); memset(arc_a, 0, sizeof(ArcNode)); arc_a->adj = index_b; arc_a->weight = weight; if (graph->data[index_a].firstArc == NULL) { graph->data[index_a].firstArc = arc_a; } else { ArcNode *p = graph->data[index_a].firstArc; while (p->nextArc != NULL) { p = p->nextArc; } p->nextArc = arc_a; }}pQueue CreateQueue() { pQueue q = (pQueue) malloc(sizeof(Queue)); memset(q, 0, sizeof(Queue)); return q;}void EnQueue(pQueue q, VNode node) { q->data[q->end++] = node;}VNode DeQueue(pQueue q) { return q->data[q->start++];}bool Empty(pQueue q) { if (q->start == q->end) { return true; } else { return false; }}void ShortestPath(pGraph graph) { // 最短路径数组 int path[graph->vexnum]; bool visit[graph->vexnum]; for (int i=0; ivexnum; i++) { visit[i] = path[i] = 0; } // wfs 队列 pQueue q = CreateQueue(); EnQueue(q, graph->data[0]); visit[0] = true; while (!Empty(q)) { // 队列不为空就一直 wfs VNode p = DeQueue(q); // 取出一个顶点 // 将未访问连通点添加到队列 ArcNode *arc = p.firstArc; while (arc!=NULL) { // 将未访问顶点入队列 if (visit[arc->adj]==false) { EnQueue(q, graph->data[arc->adj]); } // 判断到该顶点的权值 if (path[arc->adj]==0 || path[arc->adj] > path[p.index] + arc->weight) { // 如果没有路径，添加路径 path[arc->adj] = path[p.index] + arc->weight; } arc = arc->nextArc; } } // 输出结果 for (int i=0; ivexnum; i++) { printf("%ct", graph->data[i].val); } printf("n"); for (int i=0; ivexnum; i++) { printf("%dt", path[i]); } printf("n");}
结果
output:a b c d e f0 0 10 50 30 60