精华内容
下载资源
问答
  • Floyd-Warshall算法是求解任意两点最短路的有力武器。其也适用于存在负边的情况。DP思路,假设只使用前K个点时i到j的最短距离为d[k][i][j] 那么,使用前K+1个点就可以分成两种情况 ①i到j的最短路用到了第K+1个点...

    Floyd-Warshall算法是求解任意两点最短路的有力武器。其也适用于存在负边的情况。

    DP思路,假设只使用前K个点时i到j的最短距离为d[k][i][j]
    那么,使用前K+1个点就可以分成两种情况
    ①i到j的最短路用到了第K+1个点(d[k+1][i][j] = d[k][i][j])
    ②i到j的最短路没有用到第K+1个点(d[k+1][i][j] = d[k][i][k]+d[k][k][j]);
    所以,d[k+1][i][j] = min(d[k][i][j],d[k][i][k]+d[k][k][j])

    使用滚动数组,就可以写成二维数组的形式
    d[i][j] = min(d[i][j],d[i][k]+d[k][j])

    Floyd算法可以在O(V^3)的时间内解出,判断图中是否有负圈,只需要检查是否存在d[i][i]是负数的顶点i就可以了。

    代码

    //d[i][j]表示i->j的权值,不存在时设为INF 但是d[i][i]设为0
    for(int k = 0 ; k < V ; k ++) {
        for(int i = 0 ; i < V ; i ++) {
            for(int j = 0 ; j < V ; j ++) {
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }

    由于实现起来非常简单,如果复杂度在可以承受的范围之内,单源最短路也可以使用Floyd-Warshall算法来进行求解。

    在有向图中,如果需要判断每两个点是否存在路径,那么也可以用Floyd算法来进行传递闭包
    只需要改成d[i][j] = d[i][j] || (d[i][k]&&d[k][j])即可(预处理也要变化)

    展开全文
  • ps:本来是复习图论的,最后变成了... 两点之间最短路是求,固定起点和终点求最短路 两者没有根本区别,复杂度也是一样的 1,单源最短路1 bellman-ford算法 核心算法: d[i]=min(d[j]+(从顶点j到顶点i边的权值...

    ps:本来是复习图论的,最后变成了预习,隔了一段时间简直了,重新学过!

    哈哈哈哈哈哈哈,,真的菜啊!

     

       单源最短路问题是求,,固定一个起点,求它到其他所有点的最短路问题。

      两点之间最短路是求,固定起点和终点求最短路

    两者没有根本区别,复杂度也是一样的

     

    1,单源最短路1 bellman-ford算法

    核心算法:

    d[i]=min(d[j]+(从顶点j到顶点i边的权值),d[i])

    d【i】表示任意点到顶点i的最短距离

    一般初始化为INF,,然后起点d【s】初始化0。

    只要图中不存在负圈(负圈是指两点间权值为负数所形成的圈)更新操作就是有限的

    struct edge// 从顶点from——>to的权值为cost的边
    {
        int from;   
        int to;
        int cost;
    };
    edge es[maxn];  //
    int d[maxn];    //最短距离
    int v,b;        //分别为顶点和边数
    void bellman(int s)//从顶点开始递归
    {
       for(int i=0;i<v;i++)
            d[i]=INF;//先把所有顶点的最短距离设为最大,排除自圈
       d[s]=0;//初始化起点
       while(true)
       {
           bool vis=false;
           for(int i=0;i<b;i++)
           {
               edge e=es[i];
               if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost)
               {
                   d[e.to]=d[e.from]+e.cost;
                   update=true;
               }
           }
           if(!update)break;
       }
       
    }

    算了找到了大佬的详细思路,我看懂了再来补把

     

    bellman-ford算法:http://www.wutianqi.com/?p=1912

    附上自己盲敲的代码,和大佬的一样

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<queue>
    #include<set>
    #include<algorithm>
    #include<map>
    #define maxn 1000
    #define inf 100000
    using namespace std;
    struct node{
       int from,to,cost;
    }edge[maxn];
    int d[maxn];
    int n,bian,changdu,s;//节点数,边数,边长,起点
    void init()
    {
        cin>>n>>bian>>s;
        for(int i=0;i<n;i++)
            d[i]=inf;
            d[s]=0;
       for(int i=0;i<bian;i++)
       {
           cin>>edge[i].from>>edge[i].to>>edge[i].cost;
           if(edge[i].from==s)
           {
               d[edge[i].to]==edge[i].cost;
           }
       }
    }
    void rex(int from,int to,int cost)
    {
        if(d[to]>d[from]+cost)
        {
            d[to]=d[from]+cost;
        }
    }
    bool bellman()
    {
        for(int i=0;i<n-1;i++)
            for(int j=0;j<bian;j++)
        {
            rex(edge[j].from,edge[j].to,edge[j].cost);
        }
        bool flag=1;
        for(int k=0;k<bian;k++)
        {
            if(d[edge[k].from]>d[edge[k].to]+edge[k].cost)
            {
                flag=0;
                break;
            }
        }
        return flag;
    }
    int main()
    {
          init();
          if(bellman())
          {
              for(int i=0;i<=n;i++)
              {
                  cout<<d[i]<<endl;
              }
          }
          return 0;
    }

     

     

    dijkstra算法:http://www.wutianqi.com/?p=1890

     

    查错查了两个小时啊,我tm开心。

    // 普通版迪杰斯特拉   o(n*n)

    //#include<iostream>
    //#include<cstdio>
    //#include<cstring>
    //#include<cmath>
    //#include<queue>
    //#include<set>
    //#include<algorithm>
    //#include<map>
    //#define maxn 1000
    //#define inf 100000
    //using namespace std;
    //int n,bian;
    //int mp[maxn][maxn];
    //int u,v,cost;
    //int dis[maxn];
    //int pre[maxn];
    //void init()
    //{
    //    cin>>n>>bian;
    //    //memset(mp,inf,sizeof(mp));
    //    for(int i=1;i<=n;i++)
    //    for(int j=1;j<=n;j++)
    //    mp[i][j]=inf;
    //    for(int i=0;i<bian;i++){
    //        cin>>u>>v>>cost;
    //        mp[u][v]=cost;
    //        mp[v][u]=cost;
    //    }
    //    for(int i=1;i<=n;i++)
    //    {
    //        dis[i]=inf;
    //    }
    //}
    //void dijkstra(int n,int v)
    //{
    //    bool vis[maxn];
    //    for(int i=1;i<=n;i++)
    //    {
    //        vis[i]=false;
    //        dis[i]=mp[v][i];
    //        if(dis[i]==inf)
    //        {
    //            pre[i]=0;
    //        }
    //        else pre[i]=v;
    //    }
    //    dis[v]=0;
    //    vis[v]=true;
    //    for(int i=2;i<=n;i++)
    //    {
    //            int u=v;
    //            int mazz=inf;
    //            for(int j=1;j<=n;j++){
    //        if(!vis[j]&&dis[j]<mazz)//换dis最小的顶点继续查找
    //        {
    //                u=j;
    //                mazz=dis[j];
    //        }
    //        }
    //        vis[u]=true;
    //        for(int k=1;k<=n;k++)//更新顶点上的dis
    //        {
    //            if(!vis[k]&&mp[u][k]<inf)
    //            {
    //                if(dis[k]>mp[u][k]+dis[u]){
    //                    dis[k]=mp[u][k]+dis[u];
    //                    pre[k]=u;
    //                }
    //            }
    //        }
    //
    //    }
    //}
    //void chazhaolujing(int *pre,int v,int n)
    //{
    //    int tot=1;
    //    int que[maxn];
    //    que[tot++]=n;
    //    int tem=pre[n];
    //    while(tem!=v)
    //    {
    //        que[tot]=tem;
    //        tot++;
    //        tem=pre[tem];
    //    }
    //    que[tot]=v;
    //    for(int i=tot;i>=1;i--)
    //    {
    //        if(i!=1)cout<<que[i]<<"-->";
    //        else cout<<que[i]<<endl;
    //    }
    //
    //}
    //int main()
    //{
    //     init();
    //     dijkstra(n,1);
    //     cout<<dis[n]<<endl;
    //     chazhaolujing(pre,1,n);
    //     return 0;
    //}

     

    //5
    //7
    //1 2 10
    //1 4 30
    //1 5 100
    //2 3 50
    //3 5 10
    //4 3 20
    //4 5 60
    //输出数据:
    //60
    //1 -> 4 -> 3 -> 5


    //优先队列优化版的迪杰斯特拉   0(n*logn)

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<queue>
    #include<set>
    #include<algorithm>
    #include<map>
    #define maxn 1000
    using namespace std;
    const int inf=1e9+7;
    vector<pair<int ,int> >e[maxn];//建立图
    int dis[maxn];
    void init()
    {
        for(int i=0;i<maxn;i++)
            e[i].clear();
        for(int i=0;i<maxn;i++)
            dis[i]=inf;
    }
    int n,m;
    void dijkstra(int s)
    {
       priority_queue<pair<int,int> >q;
       dis[s]=0;
       q.push(make_pair(-dis[s],s));
       while(!q.empty())
       {
           int now=q.top().second;
           q.pop();
           for(int i=0;i<e[now].size();i++)
           {
               int v=e[now][i].first;//为了用起来方便而赋值
               if(dis[v]>dis[now]+e[now][i].second)//更新顶点的dis值
               {
                   dis[v]=dis[now]+e[now][i].second;
                   q.push(make_pair(-dis[v],v));
               }
           }
       }
    }
    int main()
    {
        while(cin>>n>>m)
        {
            int i,j;
            init();
            for(i=0; i<m; i++)
            {
                int x,y,z;
                scanf("%d %d %d",&x,&y,&z);
                e[x].push_back(make_pair(y,z));//e[x].push_back(y);
                e[y].push_back(make_pair(x,z));
            }
            int s,t;
            scanf("%d %d",&s,&t);
            dijkstra(s);
             if(dis[t]==inf)cout<<"-1"<<endl;
           else cout<<dis[t]<<endl;
       }
      return 0;
    }

    //Sample Input
    //3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2
    //
    //
    //Sample Output
    //2 -1

     

     

     floyd算法:http://www.wutianqi.com/?p=1903

     

    转载于:https://www.cnblogs.com/huangzzz/p/8324814.html

    展开全文
  • 算法作用求给定图中任意两点间的短距离时间复杂度O(v^3) V是顶点个数代码实现(3个for)g是用邻接矩阵传入的图, 如果两点之间没有路径, 设成inf, 否则设成边权, n是顶点个数, 顶点编号默认0~n-1, 最后i, j点的最短...

    算法作用

    求给定图中任意两点间的最短距离

    时间复杂度

    O(v^3) V是顶点个数

    代码实现(3个for)

    g是用邻接矩阵传入的图, 如果两点之间没有路径, 设成inf, 否则设成边权, n是顶点个数, 顶点编号默认0~n-1, 最后i, j点的最短路径在g[i][j]中

    void floyd(int g[][], int n) {
        for(int k = 0; k < n; ++k) 
            for(int i = 0; i < n; ++i) 
                for(int j = 0; j < n; ++j) 
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    }

    算法拓展

    可用用floyd判环g[i][j]表示i, j之间有路, 如果g[i][j] = 1 并且g[j][i]=1 那么i, j之间有环, 同时取最小值应该改成二进制的或运算

    算法证明

    根本思想方法来自动态规划;
    假设现在已经有了从i到j的最短路, 那么有两种情况:
    为方便证明给出图例
    这里写图片描述
    图1. floyd简单证明图

    可以知道i到j的最短路是i->k1->k2->k3->j
    那么直接给出转移方程g[i][j] = min(g[i][j], g[i][k] + g[k][j]) 代表的意思是g[i][j]之间的最短路等于
    1. 本来i到j的距离
    2. i 经过一个中间点k再到j
    这些路中取最小
    意思也很好理解: i到j的最短距离要么是i到j的本来就有的距离(上图的100的边权) 要么先从i到k求到最短距离, 然后再从k到j找到最短距离, 两者加起来即可

    代码实现的具体过程及思路

    一个一个的加点, 直到加完所有点
    比如本来有了图g
    1. 加入0号点, 那么图g中和0有关的可以互相到达的两点的最短路径就找出来了
    2. 加入1号点, …..
    3. 加入2号点, …..
    ……

    为什么能实现呢?
    比如在第三步中的加入2号点,
    1. 任意两个点的最短路径如果和2号点有关, 那么最短路径一定是g[i][2] + g[2][j], 而在前面的步骤中我已经求出了g[i][2] 和g[2][i], 所以在取min的过程中更新了g[i][j]
    2. 如果和2号点无关, 那么g[i][j]一定在是前面求出的最小步骤
    举个例子:
    加入求1 到 4 的最短路径: 假设是1 –> 3 –> 0 –> 4
    1. 加入0点, 那么我就求出了3到4的最短路径也就是3 –> 0 –> 4这条路
    2. 加入1点, 由于是这条路的起点, 所以其实他是不变的, 也可以理解成它求出了1–>这条路
    3. 加入2点, 由于这条最短路不包含2点, 所以对这条路没有影响
    4. 加入3点, 求出1到4的最短路径, 因为在前面已经求出了1–>3的最短路径和3 –> 4的最短路径, 所以这里的min操作就可以取到1 –> 3 –> 0 –> 4这条路径了
    ……
    如此下去, 只要取完所有的n个点, 就求出了解了, 动态规划思想好的应该更容易理解这些……

    复杂度证明

    明显的3重循环 所以复杂度是O(v^3) v是顶点个数

    展开全文
  • floyd算法-求图中任意两点最短路

    千次阅读 2017-12-19 10:35:18
    floyd算法是一种可以在o(v^3)求出一个图中任意两点最短路的算法 输入:邻接矩阵d 输出:直接在d上面修改,每个元素d(i,j)代表点i到点j的最短路 这个算法的代码非常短,一眼看上去非常暴力 for(int k=1;k;k++) ...

    floyd算法是一种可以在o(v^3)求出一个图中任意两点最短路的算法

    输入:邻接矩阵d

    输出:直接在d上面修改,每个元素d(i,j)代表点i到点j的最短路

    这个算法的代码非常短,一眼看上去非常暴力

    for(int k=1;k<=v;k++)
             for(int i=1;i<=v;i++)
                    for(int j=1;j<=v;j++)
                          d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

    思路大概是这样:这里用到了dp的方法,状态转移方程基本上就是
    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    i,j,k用于遍历所有节点,对于每一对节点i,j,若从i到j的直接距离比从i到k再到j的距离还要长,那么根据最短路的统一思想,可以对它俩进行松弛,这个方程又同时是一个松弛。

    然后每个点到自身的距离为0(邻接矩阵里面就d[i][i]都初始化成0),作为状态转移的一种终止条件。

    总的来看,floyd算法就是dp的把整个图松弛了一遍。

    以hdu1596

    find the safest road

    为例


    这个题里面换汤不换药的把值换成了0~1区间里面的浮点数,最短路换成了路上值的乘积,稍作修改即可、

    #include <bits/stdc++.h>
    
    using namespace std;
    const int maxn=1005;
    float d[maxn][maxn];
    int v;
    void init()
    {
        for(int i=1;i<=v;i++)
        {
            for(int j=1;j<=v;j++)
            {
                scanf("%f   ",&d[i][j]);
            }
        }
    }
    
    int main()
    {
        while(cin>>v)
        {
            init();
            for(int k=1;k<=v;k++)
                for(int i=1;i<=v;i++)
                    for(int j=1;j<=v;j++)
                        d[i][j]=max(d[i][j],d[i][k]*d[k][j]);
            int c,c1,c2;
            cin>>c;
            while(c--)
            {
                cin>>c1>>c2;
                if(d[c1][c2]==0)cout<<"What a pity!"<<endl;
               else printf("%.3f\n",d[c1][c2]);
            }
    
        }
        return 0;
    }
    


    展开全文
  • Floyed算法任意两点间的最短路) 可以处理存在负边的情况,也可以判断是否存在负环。 对于最短路我们之前接触的都是单源最短路径,即起点固定,求该点开始到其他点的最短路径,但是如果我们想要求得任意两点间的...
  • 本质是动态规划,O(n^3)算法思路设D[k,i,j]表示“经过若干个编号不超过k的节点”从i到j的最短路该问题可划分为个子问题:1.经过编号不超过k-1的节点从i到j 2.从i先到k再到jD[k,i,j]=min(D[k-1,i,j],D[k-1,i,k]+D...
  • 1 // 求解任意两点间的最短路径问题 2 // Floyed-Warshall算法 3 // 复杂度O(N^3),N为顶点数 4 5 #include <cstdio> 6 #include <iostream> 7 8 using namespace std; 9 // 用dp的思路来求解...
  • 求解任意两点最短路问题也叫多源最短路径问题。 可解决途径 一种方法是把图中每个点当做源点重复算n次Dijkstra 算法(Dijkstra是求单源最短路径的算法),时间复杂度O(n^3),据说可以优化成O(n^2logn)。 另一...
  • 这一算法与之前的Bellman-F=Ford算法一样,都... 1 // 求解任意两点间的最短路径问题 2 // Floyed-Warshall算法 3 // 复杂度O(N^3),N为顶点数 4 5 #include <cstdio> 6 #include <iostream> 7 ...
  • 刚开始的时候一直不明白插的顺序为什么不会对最后的结果有影响----一直不懂这个算法--- 今天看见他们都学会了-.-终于把我也带会了-- 对于原理的理解我还是通过输出每一步更新后的结果搞明白的 开始一直不...
  • 最短路算法分析

    2019-05-06 12:22:00
    最短路算法分析 如下图所示,我们把边带有权值的图称为带权图。边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相连。最短路就是指连接两点的这些路径中最短的一条。 对于所有求最短路的算法...
  • Dijkstra最短路算法

    2018-08-16 12:16:43
    上周我们介绍了神奇的只有五行的Floyd最短路算法,它可以方便的求得任意两点的最短路径,这称为“多源最短路”。本周来来介绍指定一个点(源点)到其余各个顶点的最短路径,也叫做“单源最短路径”。例如求下图中的1...
  • 最短路算法模板

    2015-08-24 20:38:48
    最短路算法 - Floyed 适合于有向图和无向图,并且是解决权值不全为负的最短路问题 利用动态规划解决任意两点间的最短路径的算法 时间复杂度是O(n^3),时间复杂度比较高,不适合计算大数据 相关运用: 如果是...
  • 最短路算法

    2017-08-06 07:25:00
    最短路径问题旨在寻找图中两节点之间的最短路径,常用的算法有以下...2 Dijkstral只能求出任意点到达源点的最短距离(不能求出任意两点之间的最短距离),同时适用于有向图和无向图,复杂度为O(n^2). 3算法的过程:...
  • 最短路算法总结

    2018-07-29 21:33:45
    Floyed-Warshall算法,是属于多源最短路径算法,是来计算任意两点之间的最短路径算法。这个算法核心代码就只有五行,基本思想是:最开始只允许经过1号顶点进行,接下来只允许经过1号和2号中转......允许经过1至n号...
  • Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以...
  • 最短路算法总结(超详细~)

    千次阅读 2020-04-11 23:09:44
    文章目录最短路算法框架朴素Dijkstra算法堆优化版Dijkstra算法 最短路算法框架 最短路有五种算法,分别适用不同的情况。 单源最短路: 求一个到其他的最短路 多源最短路: 求任意两的最短路 稠密图用邻接...
  • 关于最短路算法

    2017-12-03 20:47:00
    spfa:看了一下,感觉和bfs挺像的,不同的是bfs到达的点只添加一次,spfa算法就是只要能...folyd:最好理解的,三次循环,外层的循环是可以经过的中间的点,这个算法处理后,可以求出任意两点的最短路径; 转载...
  • Floyd最短路算法

    2020-03-10 21:54:21
    求出一个图中任意两点间最短的距离; 2. 解析 两点间距离只有两种情况: 1、 两点直接相连就是短距离 2、 两点之间经过某些点使得路径最短 可以得到这样的式子:d[i][j]=min(d[i][j],d[i][k]+d[k][j]); 因为经过的...
  • 最短路算法理解

    2017-02-27 19:09:15
    多源最短路: 核心代码: for(int p=1; p; p++) for(int i=1; i; i++) for(int j=1; j;... dis[i][j] = min(dis[i][p]+...理解:此代码是由子问题——“特定点i到特定点j的最短路”扩展成“任意两点间的最短路”问题的
  • Floyd是多源最短路算法,可得图中任意两点间的最短路。 本质上是枚举中间点,属于动态规划。 时间复杂度为O(n^3),用邻接矩阵实现。 for(int k=1;k<=n;k++)//k为枚举的中间点 for(int i=1;i<=n;i++) for(int...
  • 算法 -LCA最近公共祖先求最短路算法 [算法定义及适用范围] LCA(最近公共祖先)是一种树上的算法,求任意两点A,B的最近公共祖先。一幅n个顶点,n-1条边的图就认可以认为这幅图是一棵树。 如下图是一幅n个顶点,n-1...
  • JavaScript与Dijkstra 最短路算法

    千次阅读 2018-04-24 21:57:14
    Floyd 最短路算法用于求解任意两点的最短路径,称为“多源最短路”。下面我们介绍指定一个点到其他各个顶点的最短路径,叫做:单源最短路径。 下面我们还是先给出本篇文章讲解依赖的图: 数据结构 同样,...
  • 弗洛伊德最短路算法

    2017-12-04 00:18:07
    暑假,小哼准备去一些城市旅游。有些城市之间有公路,有些城市...我们现在需要求任意两个城市之间的最短路程,也就是求任意两之间的最短路径。这个问题这也被称为“多源最短路径”问题。 现在需要一个数据结构

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 328
精华内容 131
关键字:

任意两点最短路算法是