多源最短路径 Floyd 算法（有向图） C实现 ~
本文共 4569 字，大约阅读时间需要 15 分钟。
Floyd算法过程：
1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i][j]=d，d表示该路的长度；否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i][j]表示从Vi到Vj需要经过的点，初始化D[i][j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值变小，则D[i][j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。
Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次 ，也要高于执行|V|次 。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。缺点：时间复杂度比较高，不适合计算大量数据
核心代码：
void Floyd(Graph g) { int i, j; for(i = 0; i < g.vex_num; i++ ){ for(j = 0 ; j < g.vex_num; j++){ dist[i][j] = g.edge[i][j]; if(g.edge[i][j] == 0 || g.edge[i][j] == INFINITY)//初始化路径（关键） path[i][j] = NOTEXIST; else path[i][j] = j; } } int k; for(k = 0; k < g.vex_num; k++ ){ for(i = 0; i < g.vex_num; i++ ){ for(j = 0; j < g.vex_num; j++ ){ if(dist[i][j] > dist[i][k] + dist[k][j]){ dist[i][j] = dist[i][k] + dist[k][j]; path[i][j] = k; } } } } } 打印路径：
void print_path(Graph g,int u, int v) {// while(u != v){ (1)非递归打印 // printf("%c->",g.vex[u]);// u = path[u][v];// }// printf("%c",g.vex[u]); //(2)递归打印 printf("%c",g.vex[u]); if(u != v){ printf("->"); print_path(g,path[u][v],v); } } void traversal(Graph g) { int i, j; for(i = 0; i 完整代码实现:
#include#include #include #define INFINITY 65535#define MAXVEX 100#define NOTEXIST -1bool visited[MAXVEX];int path[MAXVEX][MAXVEX];int dist[MAXVEX][MAXVEX];typedef char VertexType;typedef int EdgeType; typedef struct Graph { VertexType vex[MAXVEX]; EdgeType edge[MAXVEX][MAXVEX]; int vex_num, edge_num; }Graph; void init_graph(Graph *g) { 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; } } } 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 (g.vex[i] == ch) return i; } return -1; } void create_graph(Graph *g) { int i, k; //printf("请输入顶点数与边数:\n"); scanf("%d%d", &g->vex_num, &g->edge_num); init_graph(g);// 初始化 //printf("请输入顶点信息:\n"); for (i = 0; i < g->vex_num; i++) { //scanf("%c", g->vex[i]); g->vex[i] = read_char(); } //printf("请输入边的信息:\n"); char c1, c2; int p1, p2,w; for (k = 0; k < g->edge_num; k++) { c1 = read_char(); c2 = read_char(); scanf("%d", &w); p1 = get_pos(*g, c1); p2 = get_pos(*g, c2); g->edge[p1][p2] = w;//有向边的权重 } } 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("%5c", '*'); else { printf("%5d", g.edge[i][j]); } } printf("\n"); } } void Floyd(Graph g) { int i, j; for(i = 0; i < g.vex_num; i++ ){ for(j = 0 ; j < g.vex_num; j++){ dist[i][j] = g.edge[i][j]; if(g.edge[i][j] == 0 || g.edge[i][j] == INFINITY) path[i][j] = NOTEXIST; else path[i][j] = j; } } int k; for(k = 0; k < g.vex_num; k++ ){ for(i = 0; i < g.vex_num; i++ ){ for(j = 0; j < g.vex_num; j++ ){ if(dist[i][j] > dist[i][k] + dist[k][j]){ dist[i][j] = dist[i][k] + dist[k][j]; path[i][j] = k; } } } } }int dfs(Graph g, int i) { int j; visited[i] = true; for(j = 0; j < g.vex_num; j++ ){ if(!visited[j] && i != j && g.edge[i][j] != INFINITY){ dfs(g, j); } } } int is_connected(Graph g, int u, int v)//利用 深度优先搜索判断图中u, v两点是否连通 { int i, flag; for(i = 0; i < g.vex_num; i++ ){ visited[i] = false; } dfs(g, u); if(visited[v] == true) return 1; else return 0; } void print_path(Graph g,int u, int v) {// while(u != v){ (1)非递归打印 // printf("%c->",g.vex[u]);// u = path[u][v];// }// printf("%c",g.vex[u]); //******************************//(2)递归打印 printf("%c",g.vex[u]); if(u != v){ printf("->"); print_path(g,path[u][v],v); } } void traversal(Graph g)//打印各路径 { int i, j; for(i = 0; i
你可能感兴趣的文章
Python学习笔记——云计算
查看>>
Python学习笔记——运维和Shell
查看>>
Python学习笔记——nginx
查看>>
Python学习笔记——自动化部署
查看>>
Python学习笔记——多任务-协程
查看>>
Python学习笔记——WSGI、mini-web框架
查看>>
Python学习笔记——闭包、装饰器
查看>>
Python学习笔记——mini-web框架 添加路由、MySQL功能
查看>>
Python学习笔记——mini-web框架 添加log日志、路由支持正则
查看>>
Python学习笔记——元类、实现ORM
查看>>
Python学习笔记——Celery
查看>>
Python学习笔记——数据分析之Matplotlib绘图
查看>>
Python学习笔记——数据分析之工作环境准备及数据分析建模理论基础
查看>>
Python学习笔记——数据分析之Seaborn绘图
查看>>
Python学习笔记——数据分析之Bokeh绘图
查看>>
Python学习笔记——数据分析之数据可视化工具实战案例：世界高峰数据可视化
查看>>
Python学习笔记——科学计算工具Numpy
查看>>
Python学习笔记——数据分析之数据分析工具Pandas
查看>>
Python学习笔记——Pygame之基础知识
查看>>
Ubuntu 18.04双系统安装教程-超详细（原系统Win7，解决安装完成后启动Ubuntu进入GLUB的问题）
查看>>