最短路径——floyd算法代码(c语言)
2024-08-25 03:46:22
最短路径问题
昨天自己试了试写一下dijkstra的算法博客
今天来更floyd算法,感觉非常简单果然暴力才是解决一切的王道
一、总体思想
floyd算法就是每一次从邻接矩阵选取一个顶点k,然后再去矩阵中遍历两个顶点i,j,看看是i→j的路径短,还是i→k→j的路径短,就是完全的暴力,算法和代码非常简单
二、代码实现
void Floyd(Graph G)
{
int arr[G.vexnum][G.vexnum];
for(int i = ; i < G.vexnum; i++)
for(int j = ; j < G.vexnum; i++)
arr[i][j] = G.edge[i][j]; for(int k; k < G.vexnum; k++)
for(int i = ; i < G.vexnum; i++)
for(int j = ; j < G.vexnum; j++)
if(arr[i][j] > arr[i][k] + arr[k][j])
arr[i][j] = arr[i][k] + arr[k][j];
}
三、代码解释
其实看上面的代码量和代码就知道这个算法很简单 =_=
传入Floyd算法的参数是Graph G
首先开辟一个二维数组arr[][],并且把图的邻接矩阵G.edge[][]赋值给arr[][],算法的主要思想就是来修改arr[][]值暴力出最短路径
int arr[G.vexnum][G.vexnum];//开辟数组arr[][]接收图G.edge[][]的值
for(int i = ; i < G.vexnum; i++)
for(int j = ; j < G.vexnum; i++)
arr[i][j] = G.edge[i][j];//遍历赋值
然后就是每次选择一个顶点k,再去找两个顶点i,j,对比看看是i→j的路径短,还是i→k→j的路径短
也就是arr[i][j] 和 arr[i][k] + arr[k][j]两个的值谁的比较小,然后修改arr[][]一直到遍历完毕
for(int k; k < G.vexnum; k++)//选取k顶点
for(int i = ; i < G.vexnum; i++)
for(int j = ; j < G.vexnum; j++)//再选取i,j两个顶点
if(arr[i][j] > arr[i][k] + arr[k][j])//判断i→j的路径和i→k→j的路径谁比较短
arr[i][j] = arr[i][k] + arr[k][j];//如果i→k→j的路径更短,则修改数组arr[][]
写完感觉好短。。不过确实没啥写的,就是O(n3)的暴力,而且这个算法能计算含有负权值的图,dijkstra就不行
虽然dijkstra的算法只有O(n2),但是它只有一个顶点到剩下顶点的最短路径,如果还是要计算每个点到每个点的最短路径,其实和Floyd一样,也是O(n3)
最重要的是 ——Floyd算法他好记啊!
最新文章
- Qt——透明无边框Widget的bug
- 关于listView 中的聚焦问题
- windowDialog销毁页面的问题
- [C#]多线程下载
- ARP协议格式、ARP运行机制入门学习
- drawer principle in Combinatorics
- hdu 2883 kebab 网络流
- [ES6] 18. Map
- Xamarin 实现android gridview 多选
- ThinkPHP3.1新特性: 多层MVC支持
- python代码优化技巧
- cf445B DZY Loves Chemistry
- 利用CoreAnimation实现一个时间的进度条
- [BZOJ 3498] [PA 2009] Cakes
- SpringBoot系列: Eclipse+Maven环境准备
- 阿里P9架构师讲解从单机至亿级流量大型网站系统架构的演进过程
- Python之字符编码(一)
- Git 配置环境及常用命令整理
- SQL SERVER数据库维护与重建索引
- git分支 远程协作