最短路径——弗洛伊德算法

这篇具有很好参考价值的文章主要介绍了最短路径——弗洛伊德算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

求每一对顶点之间的最短路径

对于这类最短路径问题,DIF算法也可以解决,只需要定义一个二维数组,以数组的横坐标作为有向网顶点的下标循环n次依次求解各个源点到其余顶点的最短路径,时间复杂度为O(n^3)

由于弗洛伊德算法求解该问题的的时间复杂度同为O(n^3),而且思路简单及代码实现简洁,故采用弗洛伊德算法(Floyd)求解该类问题。

链接

欲了解迪杰斯拉特算法求解单源点到其余顶点的最短路径可点击链接:http://t.csdn.cn/miPKQ

弗洛伊德算法

算法实现思想

总结为一句话即:任意一个顶点都有可能作为其他任意两顶点间最短路径的中转点,更新两顶点间的更短路径,且中转点的顺序交换没有影响,通过依次使n个顶点充当一次中转点以求解任意顶点间的最短路径。

图解(1)

vue实现弗洛伊德算法,C++,数据结构与算法,数据结构,图论,Powered by 金山文档

由图可见,若将B称为一级中转点,那么A通过一级中转点B获取到达顶点C的更短路径

图解(2)即使B没有作为以及中转点,其依旧有可能充当其他级别的中转点。

vue实现弗洛伊德算法,C++,数据结构与算法,数据结构,图论,Powered by 金山文档

由图可见,即使B没有作为A到C的一级中转点(直接中转)但是B作为D到C的一级中转点,为A借助中转点D获取到达C的更短路径打下了基础。可见,每一个顶点都有可能作为任意两点的直接或间接中转点,因此主循环需要循环n次,依次将图中的顶点vk作为其余顶点间的路径<vi,vj>的中转点判断该顶点是否可以作为<vi,vj>的中转点。若可以,则更新<vi,vj>的最短路径。其数学表达式为,假设Dis(vi,vj)表示顶点vi到顶点vj的路径权值,假如Dis(vi,vj)>Dis(vi,vk)+Dis(vk,vj),则Dis(vi,vj)=Dis(vi,vk)+Dis(vk,vj)。

同时,各个顶点充当中转点的顺序不影响求解任意顶点间最短路径的效果。如图(2)所示,若B先充当中转点再到D,则D先通过B连通C,即D->B->C。再到D充当中转点时,A通过D连通C,即A->D->B->C为最短路径;若D先充当中转点再到B,则A先通过D连通B,即A->D->B.再到D通过B连通C,即A->D->B->C.可见,各个顶点充当中转点的顺序不影响求解任意顶点间最短路径的效果。

数据结构说明

本例将采取邻接矩阵作为有向网的存储结构,其中Mvnum为最大顶点数VerType为顶点类型(此处用char),ArcType为弧的权值(int),infs表示无穷大,表示<vi,vj>无路可通

辅助数组将采用int D[Mvnum][Mvnum]表示任意两个顶点之间最短路径的状态,且D的初态等同于数组G.arcs(存储任意顶点间的路径);采用int Path[Mvnum][Mvnum]表示在当前的最短路径<vi,vj>中,顶点vj的直接前驱顶点下标为Path[i][j],初始化时,若<vi,vj>存在弧,则Path[i][j]=i。

n阶方阵D的数学含义:规定D(-1)==G.arcs,假设D(k+1)表示方阵D经过v0,v1,v2……vk等中转点更新后的状态,则

vue实现弗洛伊德算法,C++,数据结构与算法,数据结构,图论,Powered by 金山文档

D(k+1)[i][j]=Min{D(k)[i][j],D(k)[i][k]+D(k)[k][j]}

算法实现

//文件名:AMGraph.h
#pragma once
#include<iostream>
using namespace std;

//邻接矩阵存储有向网
#define Mvnum 100  //最大顶点数
typedef char VerType;  //顶点数据类型
typedef int ArcType;  //弧的权值
typedef struct AMGraph {
    int vexnum, arcnum;
    VerType vexs[Mvnum];          //顶点信息表
    ArcType arcs[Mvnum][Mvnum];   //邻接矩阵
}AMGraph;

//创建有向网
void CreateUDN(AMGraph& G);
//文件名:AMGraph.cpp
#include"AMGraph.h"

//用邻接矩阵创建有向网
void CreateUDN(AMGraph& G)
{
    //inf表示两顶点间没有线路,距离为无穷大
    int infs = 99999999;
    //输入顶点与弧的个数
    cin >> G.vexnum >> G.arcnum;
    //判断合法性
    if (G.vexnum > Mvnum || G.arcnum > (G.vexnum - 1) * G.vexnum)
    {
        cout << "所输入信息非法" << endl;
        return;
    }
    //输入顶点的信息,类型为char
    for (int i = 0;i < G.vexnum;i++)
    {
        cin >> G.vexs[i];
    }
    //将图的边初始化
    for (int i = 0;i < G.vexnum;i++)
    {
        for (int j = 0;j < G.vexnum;j++)
        {
            if (i != j)
                G.arcs[i][j] = infs;
            else
                G.arcs[i][j] = 0;
        }
    }
    //输入权值
    for (int i = 0;i < G.arcnum;i++)
    {
        //输入v1,v2作为弧<v1,v2>的顶点以及该弧权值w
        //顶点下标从0开始
        int v1, v2, w;
        //此处省略了查找v1,v2编号的过程
        cin >> v1 >> v2 >> w;
        //判断合法性
        if (v1 == v2 || v1 >= G.vexnum || v2 >= G.vexnum
            || v1 < 0 || v2 < 0)
        {
            i--;
            continue;
        }
        if (G.arcs[v1][v2] != infs)
        {
            i--;
            continue;
        }
        //输入弧<v1,v2>的权值
        G.arcs[v1][v2] = w;
    }
    //创建完毕
}
//文件名:Floyd.h
#pragma once
#include"AMGraph.h"
//弗洛伊德算法的头文件

/*
    该算法的思想是,每一个顶点都有可能是其他任意两个顶点的中转点,
    因此有向网中的每一个顶点都需要尝试作为其他任意两个顶点的中转点
*/

//输出任意顶点之间的最短路径
void OutshortestPath_Floyd(const AMGraph& G, int(*D)[Mvnum], int(*Path)[Mvnum]);

//任意顶点之间最短路径的顶点顺序
void OutvexInPath_Floyd(const int& i, const int& j, int(*Path)[Mvnum], const AMGraph& G);
//初始化函数
void Init_Floyd(const AMGraph& G, int(*D)[Mvnum], int(*Path)[Mvnum]);

//弗洛伊德算法
void ShortestPath_Floyd(const AMGraph& G);
//文件名:Floyd.cpp
#include"Floyd.h"
//infs表示两顶点间没有线路,距离为无穷大
int infs = 99999999;
//初始化函数
void Init_Floyd(const AMGraph& G, int(*D)[Mvnum], int(*Path)[Mvnum])
{
    //D的初始状态为G.arcs[Mvnum][Mvnum]
    for (int i = 0;i < G.vexnum;i++)
    {
        for (int j = 0;j < G.vexnum;j++)
        {
            D[i][j] = G.arcs[i][j];
        }
    }
    //初始化Path,假如<vi,vj>之间弧,则vj的直接前驱为vi,否则为-1
    for (int i = 0;i < G.vexnum;i++)
    {
        for (int j = 0;j < G.vexnum;j++)
        {
            if (G.arcs[i][j] != infs && i != j)
                Path[i][j] = i;
            else
                Path[i][j] = -1;
        }
    }
}

//任意顶点之间最短路径的顶点顺序
void OutvexInPath_Floyd(const int& i, const int& j, int(*Path)[Mvnum], const AMGraph& G)
{
    if (Path[i][j] == -1)
    {
        cout << G.vexs[i];
    }
    else
    {
        OutvexInPath_Floyd(i, Path[i][j], Path, G);
        cout << "->" << G.vexs[j];
    }
}

//输出任意顶点之间的最短路径
void OutshortestPath_Floyd(const AMGraph& G, int(*D)[Mvnum], int(*Path)[Mvnum])
{
    cout << "任意两顶点之间的最短路径如下:>" << endl;
    for (int i = 0;i < G.vexnum;i++)
    {
        for (int j = 0;j < G.vexnum;j++)
        {
            if (i == j)
                continue;
            if (Path[i][j] == -1)
            {
                cout << "<" << G.vexs[i] << "," << G.vexs[j] << ">" << "无路可通!!!" << endl;
            }
            else
            {
                cout << "顶点" << G.vexs[i] << "到顶点";
                cout << G.vexs[j] << "的最短路径为:>" << D[i][j] << endl;
                //源点为vi,终点为vj
                OutvexInPath_Floyd(i, j, Path, G);
                cout << endl;
            }
        }
    }
}

//弗洛伊德算法
void ShortestPath_Floyd(const AMGraph& G)
{
    //辅助数组

    //1.任意两个顶点之间最短路径的状态数组
    //或者写为ArcType D[Mvnum][Mvnum] = { 0 };
    int D[Mvnum][Mvnum] = { 0 };
    //2.存储在当前的最短路径<vi,vj>中,顶点vj的直接前驱顶点下标为Path[i][j]
    int Path[Mvnum][Mvnum] = { 0 };

    //初始化函数
    Init_Floyd(G, D, Path);

    //将下标为k的顶点作为试探中转点
    for (int k = 0;k < G.vexnum;k++)
    {
        for (int i = 0;i < G.vexnum;i++)
        {
            for (int j = 0;j < G.vexnum;j++)
            {
                if (D[i][j] > D[i][k] + D[k][j])
                {
                    //更新弧<vi,vi>的最短路径
                    D[i][j] = D[i][k] + D[k][j];
                    //更新在最短路径<vi,vj>中,vj的直接前驱结点
                    //因为如今<vi,vj>的路径由路径<vi,vk>与<vk,vj>组成
                    //因此vj在<vi,vj>中的直接前驱等同于vj在<vk,vj>的直接前驱
                    Path[i][j] = Path[k][j];
                }
            }
        }
    }
    //输出任意顶点之间的最短路径
    OutshortestPath_Floyd(G, D, Path);
}

测试

//文件名:test.cpp
void test()
{
    AMGraph G;
    CreateUDN(G);
    ShortestPath_Floyd(G);
}


int main()
{
    test();
    return 0;
}

测试结果

vue实现弗洛伊德算法,C++,数据结构与算法,数据结构,图论,Powered by 金山文档

算法分析

显而易见,空间复杂度为O(n^2),时间复杂度为O(n^3);另外,即使使用邻接表也不方便,因为需要对比Dis(vi,vj)与Dis(vi,vk)+Dis(vk,vj)每一轮需要在顶点vi与vk中找三条边,特别不方便,不及邻接矩阵的随机访问。同时,虽然邻接表一般适合于存储稀疏网,但是对于具有n个顶点与e条边的有向网而言,后序可能需要生成n^2-e条新边网的边数激增将使邻接矩阵失去其存储稀疏网的优势,故在求解最短路径问题时,一般采用支持随机访问的邻接矩阵作为存储结构文章来源地址https://www.toymoban.com/news/detail-818179.html

到了这里,关于最短路径——弗洛伊德算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 弗洛伊德(Floyd)算法求个顶点之间最短路径问题(详解+图解)

    具体来说,弗洛伊德算法通过求解所有点对之间的最短路径来实现。在算法开始时,我们假设图中的所有节点之间都是不联通的,即它们之间的距离为无穷大。然后,我们对图进行“松弛”操作,即尝试更新每个节点之间的距离估计值,以寻找更短的路径。具体来说,对于图

    2024年02月08日
    浏览(43)
  • 【数据结构】图—弗洛伊德(Floyd)算法

    上文介绍了迪杰斯特拉(Dijkstra)算法,计算网图的某个源点到其余各个顶点的最短路径问题(边权值为非负值),本文介绍另一个求最短路径的算法——弗洛伊德算法,它是计算所有顶点到所有顶点的最短路径,其时间复杂度为 O ( n 3 ) O(n^3) O ( n 3 ) ,其算法相比Dijkstra算法更加

    2024年02月12日
    浏览(51)
  • 大话数据结构-迪杰斯特拉算法(Dijkstra)和弗洛伊德算法(Floyd)

      最短路径,对于图来说,是两顶点之间经过的边数最少的路径;对于网来说,是指两顶点之间经过的边上权值之和最小的路径。路径上第一个顶点为源点,最后一个顶点是终点。   以如下无向图为例:   我们来计算下标为0的顶点,到其他顶点的最短路径,首先定义

    2024年02月06日
    浏览(42)
  • 弗洛伊德循环查找算法-原理

    本文灵感来自哔哩哔哩视频  视频链接: 弗洛伊德循环查找算法 算法代码(java) 弗洛伊德循环查找算法中第二次相遇的地方就是循环的起始点,这个性质的证明是基于数学的原理。这是因为在第一次相遇时,慢指针 `slow` 和快指针 `fast` 已经处于同一个循环内。设链表起点到环

    2024年01月19日
    浏览(46)
  • 40.弗洛伊德(Floyd)算法

    我们此前拆解过迪杰斯特拉(Dijkstra)算法,与它一样,弗洛伊德(Floyd)算法也是用于寻找给定的加权图中顶点间最短路径的算法。该算法是1978年图灵奖获得者、斯坦福大学计算机科学系教授 罗伯特·弗洛伊德 及其团队发现的,以主要创始人 弗洛伊德 命名。 迪杰斯特拉算

    2024年02月06日
    浏览(36)
  • Floyd - Warshall (弗洛伊德算法)

    图中任意两点之间的最短路径问题 Dijkstra和Bellman-Ford也可以以所有点为源点,求出任意两点之间的最短距离,但是Dijstra不能解决带负权的的边,Bellman-Ford 效率慢点 Floyd算法考虑的是一条最短路径的中间节点,即简单路径p={v1 , v2,  ...  ,vn}上除v1和vn的任意节点 设K是p的一个

    2024年02月06日
    浏览(40)
  • 今天学习了弗洛伊德算法(floyed)

    我自己写的模板 嘿嘿 Dijkstra算法SPFA算法但是我知道还有这些,但是今天是周末哎,我有点不想学了,我今天学的是比较差劲的一个算法(但是它好像比较好记啊),改天再学其他比较好一点的算法加强自己 输入 输出 后言:提醒自己加权值是分题目来不同权值,不是像示例

    2024年02月11日
    浏览(36)
  • 力扣-202. 快乐数解析-弗洛伊德循环查找算法

    题目链接   使用代码测试一下每一代数字  可以发现 归纳一下这些简单数字就可以发现,对于任意一个非快乐数,最终会进入重复循环, ···不难发现,4即之后的结果就是新一轮循环。 那么我的第一个做法是检测4出现的次数 如果4出现次数超过两次, 那么就不是快乐数 感

    2024年01月20日
    浏览(39)
  • 算法——弗洛伊德算法(Floyd-Warshall)(图论)(c++)

    (蒟蒻的第四篇文章,希望dalao勿喷) (希望没问题) 声明: 1.本人变量定义的名称很low 2.本人用的方法也很low 3.但我觉得文章应该不low  (盲目自信) 第四篇文章讲讲Floyd算法 Floyd算法是一种寻找最短路径的常见算法,其特点是: 短,好理解(虽然其他算法也挺好理解的

    2023年04月09日
    浏览(34)
  • 12.25~12.27并查集(查找与合并),全排列,约瑟夫问题(队列,数组)upper/lower_bound,重构二叉树,最优矩阵,线段树(构建),淘汰赛(构建树,队列),医院问题(最短路,弗洛伊德

    题目背景 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 题目描述 规定:�x 和 �y 是亲戚,�y 和 �z 是亲戚,那么 �x 和 �z 也是亲戚。如果 �x,�y 是亲戚,那么 �

    2024年01月23日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包