最短路径-C++算法

C++算法之——最短路径（基础2）@2020版

前记

通过前面那份讲义，你应该对基础知识有所了解。
今天我们来看下floyed算法的实现！

复习

什么是最短路径
百度中的定义：用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

我自己的理解就是枚举得到最近的一个点，再向外进行探索直到目标点

主要内容

讲解
1、要求两点之间的最短路径，我们先假设两点间最短距离存入f[i][j]
中，
2、为了清楚表示两点的连通情况，我们会想到用特殊值，最特殊可以包括所有情况的数值就是INT_MAX ，那我们就用这个值代表两点不连通（要无限时间到达） 不要用memset初始化
3、怎么查找呢？
floyed算法十分简单 直接暴力循环即可（O（n3））

具体操作

1、判断条件及内部代码
假设要求的最短距离 i 和 j之间，k为要求最短距离的中转点
每次当i到k k到j 有距离时（不可能走不通的路去走）
所以要循环内部进行一个判断

• 而为什么不用判断i到j有没有最短距离呢？
  因为如果没有距离就是无穷大，一定不会选择

• 而为什么要判断i’到k和k到j呢?
  因为无穷大加上一个数防止与另一个数进行比较会出错
  注意最后把最短距离赋给两种的最小值

if(f[i][k]!=INT_MAX && f[k][j]!=INT_MAX){
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }

2、三重循环
通过枚举i j k来得到三个点
重点

• k要放在最外层循环中
  • 因为他是从上一层k转移过来的，所以当前的f[i][j]都应该是完成上一层循环更新的，如果k不是在最外层，那么f[i][j]就可能不是完成上一层循环后的状态，有可能有的点没有经过k-1这个点的更新。
    • 所以千万记住放在**最外层！！！**不然可能有的会过不了！！！

for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
            if(f[i][k]!=INT_MAX && f[k][j]!=INT_MAX){
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
 }

完整代码

#include <bits/stdc++.h>
using namespace std;
int s,t;
int x[1000],y[1000];
int m;
double f[1000][1000];
double get(int u,int v){
    return sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]));
}
int main(){
    int n;
    cin>>n;
    for(int i=1 ;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=INT_MAX;
            if(i==j) f[i][j]=0;
        }
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        f[u][v]=f[v][u]=get(u,v);
    }

    scanf("%d%d",&s,&t);
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
            if(f[i][k]!=INT_MAX && f[k][j]!=INT_MAX){
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
    }
    printf("%.2lf ",f[s][t]);
}

常见错误

后记

感谢大家的关注！
若有任何建议请发邮件至learning.dlq@gmail.com！