`
lovecontry
  • 浏览: 1029716 次
文章分类
社区版块
存档分类
最新评论

求最短路径之——Floyd算法

 
阅读更多

要求有向网中每两个顶点之间的最短距离,用Dijkstra算法的话,只需要将每个顶点都作为一次源点就可以,用Floyd算法的话,虽然在时间复杂度上和Dijkstra算法一样,但是形式上更为简便,整体性更好。下面是代码:

文件"graph.h"

测试文件"main.cpp"

下面是输入和输出结果:

所生成的有向网如下:


分享到:
评论

相关推荐

    最短路径——数学建模

    有好多 个经典的算法算法和例子 应该值这么多分数的

    图论:最短路径+最小生成树+中心度计算

    包含图论众多热点问题:最短路径——Dijkstra SPFA Floyd等 最小生成树的两种计算方法、三种中心度、连通分量的计算 输入文件格式按照graph_movie.txt

    Vectorized Floyd-Warshall:Floyd-Warshall 所有对最短路径算法的矢量化(快速)实现。-matlab开发

    Floyd-Warshall 算法计算给定邻接矩阵的所有对最短路径矩阵。 该算法是 O(n^3),在大多数实现中,您会看到 3 个嵌套的 for 循环。 这在 Matlab 中效率很低,所以在这个版本中,两个内部循环被向量化(因此,它运行得...

    最短路问题及其应用——最短路径

    最短路问题及其应用 大连海事大学 图论,最短路径,树,生成树,迪杰斯特拉(Dijkstra),弗罗伊德(Floyd)算法

    算法学习记录(具有详细代码)

    该压缩文件中包含动态规划,合并排序与快速排序算法,回溯,求最大字段和(穷举法、动态规划、分治法),求最小生成树(Prim算法与Kruskal算法与并查集),贪心算法,最短路径问题——基于Dijkstra算法和Floyd算法的...

    Qt和C/C++实现的可视化景点旅游信息系统——包含详细注释与txt说明文件

    5. 该项目包含 求两个景点间的最短路径的算法——Floyd 6. 该项目包含 给出道路建设(最小生成树)的算法——Kruskal 7. 该项目包含 自定义地图文件读入与写出的算法 阅读建议: 在下载压缩包后,务必细看 .txt 说明...

    acm常用代码及算法

    4.Floyd算法求每对节点间最短路径 排序/查找: 1.快速排序 2.希尔排序 3.选择法排序 4.二分查找 数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树 ...

    ACM常用代码

    数学问题: 1.精度计算——大数阶 乘 ...4.Floyd 算法求每对节点 间最短路径 排序/查找: 1.快速排序 2.希尔排序 3.选择法排序 4.二分查找 数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树

    ACM 常用代码 数学问题 计算几何 数论 图论 数据结构

    精度计算——大数阶乘 组合序列 最大公约数、...任意进制转换 叉乘法求任意多边形面积 两矢量间角度 Prim算法求最小生成树 Dijkstra算法求单源最短路径 Bellman-ford算法求单源最短路径 Floyd算法求每对节点间最短路径

    图论的一些算法——c语言、c++

    *算法:Floyd——O(V^3) *输入:加权连通图(矩阵):g *输出:最短距离长度矩阵d[][], 路径矩阵p[][] */ GraphMatrix < double > g; double d[maxV][maxV]; // 最短路径长度 int p[maxV][maxV]; // ...

    无线传感器网络节点优化问题

    问题二中,寻找一条从节点A到节点D的最短传输路径,本文将图中所给信息导成图论结构,建立图论模型,于是问题就转化为图论中求最短路径问题,因此本文设计两种算法——Floyd算法和Dijkstra算法,运用Matlab编程计算...

    程序员代码面试指南——IT名企算法和数据结构题目最优解.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    计算机算法分析与设计实验源代码共计五个程序

    动态规划法在图问题中的应用——全源最短路径问题 3. 实验要求 (1)实现Floyd算法; (2)算法的输入可以手动输入,也可以自动生成; (3)算法不仅要输出从每个顶点到其他所有顶点之间的最短路径,还有输出最短...

    Floyd——c++

    给定一个邻接矩阵文本,利用Floyd算法求出两点之间的最短路径

    数据结构课程设计——校园导游(含报告)

    单源最短路径和2点间最短路径,即Dijkstra算法与Floyd算法 另附:需要读写文件,文件中包含各个景点信息,一共十个景点。 所建的graph有10个顶点,13条边,这一点很重要,程序一开始便要用到这两个数字。 源代码...

    ACM 内部预定函数

    4.Floyd算法求每对节点间最短路径 5.解欧拉图 排序/查找: 1.快速排序 2.希尔排序 3.选择法排序 4.二分查找 高精度运算专题: 1.本专题公共函数说明 2.高精度比较 3.高精度加法 4.高精度...

    最短路径.zip_数值算法/人工智能_C/C++_

    最短路径的典型算法——Dijkstra、Floyd。使用C++语言,对算法使用类模板,可方便开发者直接调用。文件中包含了图的ADT

    ACM 算法经典代码 数据结构经典代码

    目录 一.数论 4 ...4.Floyd算法求每对节点间最短路径 排序/查找: 1.快速排序 2.希尔排序 3.选择法排序 4.二分查找 数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树

    算法和数据结构——左程云.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

Global site tag (gtag.js) - Google Analytics