算法分析设计（Floyd算法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法分析设计（Floyd算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2723字，纯文字阅读大概需要4分钟。

内容图文

1. 问题

用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵（顶点之间的最短距离矩阵），按实验报告模板编写算法。

 

 

 

 

 

 

 

2. 解析

 

3.设计

void Floyd(int n ,int m ,int path[][1000])
{
    for(int k = 1 ; k <= n ; ++ k)                               //枚举中转点，通过中转点对i，j进行松弛操作
    {
        for(int i = 1 ; i <= n ; ++ i)                       //枚举起点
        {
            for(int j = 1 ; j <= n ; ++ j)                       //枚举终点
            {
                if(path[i][k] + path[k][j] < path[i][j])         // 如果通过k节点使得 path[i][k] + path[k][j] < path[i][j] 则说明经过k节点会使得i，j之间的距离更短，更新最短距离
                    path[i][j] = path[i][k] + path[k][j];
            }
        }
    }
}

算法部分

4. 分析

时间复杂度：O(n^3)

这里需要枚举三个量，分别是中转点，起点，终点，因为三个点都属于图中的n个点，因此时间复杂度为O(n * n * n)

复杂度就是边的数量

空间复杂度：O(n ^ 2)

 

在Floyd算法中我们用二维矩阵维护从i到j的最短距离，因为需要维护任意两个节点之间的最短距离，所以所需要的空间复杂度应该是O(n * n)

 

5.代码

#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;

const int inf = 0x3f3f3f3f;                               //inf代表无穷大，在本算法中，如果path[i][j] == inf ，那么说明从节点i出发无法到达节点j
int n, m;
int p[1000][1000];                                       //用来维护图中任意两点之间的最短距离


void Floyd(int n ,int m ,int path[][1000])
{
    for(int k = 1 ; k <= n ; ++ k)                               //枚举中转点，通过中转点对i，j进行松弛操作
    {
        for(int i = 1 ; i <= n ; ++ i)                           //枚举起点
        {
            for(int j = 1 ; j <= n ; ++ j)                       //枚举终点
            {
                if(path[i][k] + path[k][j] < path[i][j])         // 如果通过k节点使得 path[i][k] + path[k][j] < path[i][j] 则说明经过k节点会使得i，j之间的距离更短，更新最短距离
                    path[i][j] = path[i][k] + path[k][j];
            }
        }
    }
}



int main()
{

    memset(p , inf , sizeof p);                         //对图path进行初始化
    cin >> n >> m;                                      //获取节点个数和边的条数
    for(int i = 1 ; i <= n ; ++ i) p[i][i] = 0;         //一个节点到它本身的最小距离肯定是0，这里我们直接修改就好了   
    for(int i = 1 ; i <= m ; ++ i)
    {
        int u ,v , val;
        cin >> u >> v >> val;                           //获取单向边的信息
        p[u][v] = min(p[u][v] , val);                   //因为我们要求图中任意两点的最小距离，因此对于点i，j之间的路线，我们只要记录最小值即可
    }
    Floyd(n , m , p);                                    //进行Floyd
    cout << "最短距离矩阵：" << endl;
    for(int i = 1 ; i <= n ; ++ i)
    {
        for(int j = 1 ; j <= n ; ++ j)
        {
            if(p[i][j] == inf) cout << -1;              //如果p[i][j] == inf , 说明从i节点出发，无法到达j节点，这里我们用-1表示无法到达
            else cout << p[i][j];
            if(j == n) cout << endl;
            else cout << " ";
        }
    }
    return 0;
}

/*
样例：

4 8
1 2 2
2 3 3
1 3 6
3 1 7
1 4 4
4 1 5
3 4 1
4 3 12


*/

完整代码

 

 

 

 

内容总结

以上是互联网集市为您收集整理的算法分析设计（Floyd算法）全部内容，希望文章能够帮你解决算法分析设计（Floyd算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---