最短路算法(小小总结一下)

摘要:
1.Dijkstra算法处理正边缘权重。。。N=M=0表示输入结束。(输入以确保从商店到现场至少有一条路线。对于这个v-1边,第一条边在第一次松弛后不能松弛。这证明了算法在没有负循环的图上的正确性。如果原始图中存在负循环:显然,对于负循环中的任何点,其最短路径将是负无穷大,因此松弛离子操作不会停止。将源点放入队列。松弛d[]后,值将更改,不在队列中的点将添加到队列中。两种解释:时间复杂度最差:O将军:O。

 

1,Dijkstra算法

(1) 处理正边权可以处理负边权,但必须是负边只存在源点s连出去的边

(2) 时间复杂度……O(V^2)

例题:

In: 输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商 店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1& lt;=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
(输入保证至少存在1条商店到赛场的路线。)

Out: 对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间

Code:

#include<iostream>

#include<stdio.h>

#include<iomanip>

using namespace std;

#define N 10000

#define MAX 100000099

int a[N][N];

int dist[N];

void input (int n,int m)

{

    int p,q,len,i,j;

    for( i=1;i<=n;i++)

    {

        for(j=1;j<=n;j++)

            a[i][j]=MAX;

        dist[i]=MAX;

    }

    for(i=0;i<m;i++)

    {

        cin>>p>>q>>len;

        if(len<a[p][q])

        {

            a[p][q]=len;

            a[q][p]=len;

        }

    }

}

void dijkstra(int n)

{

    int s[N],newdist;

    for(int i=1;i<=n;i++)

    {

        dist[i]=a[1][i];

        s[i]=0;

    }

    dist[1]=0;

    s[1]=1;

    for(i=2;i<=n;i++)

    {

        int j,tem=MAX;

        int u=1;

        for(j=2;j<=n;j++)

            if(!s[j]&&dist[j]<tem)

            {

                u=j;

                tem=dist[j];

            }

            s[u]=1;

            for(j=2;j<=n;j++)

            {

                if(!s[j]&&a[u][j]<MAX)

                {

                    newdist=dist[u]+a[u][j];

                    if(newdist<dist[j])

                        dist[j]=newdist;

   

                }

            }

    }

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m),m||n)

    {

        input(n,m);

        dijkstra(n);

        cout<<dist[n]<<endl;

    }

    return 0;

}

2.Bellman-Ford算法

如果原图中不存在负环:

s可达的任意点v的最短路至多经过v1条边。对于这v1条边,第一次松弛后第一条边不可再松弛。第二次松弛后第二条边不可再松弛,…这样便证明了算法在没有负环的图上的正确性。

如果原图中存在负环:

显然对于负环中的任何一个点,它的最短路会是负无穷,所以松弛操作不会停止。算法返回false

时间复杂度: 两个for循环O(VE)

例题(hdu2544)

Code:

#include <stdio.h>

#define MAX 1000000000

int m, n, i, j ,k;

int start, end, value;

int dis[105], edge[105][105];

int Min (int a, int b)

{

    return a < b ? a : b;

}

void Bellman (int source)

{

    for (i = 0; i <= n; ++i)

    {

        dis[i] = edge[1][i];

    }

    for (k = 2; k < n; ++k)

    {

        for (i = 1; i <= n; ++i)

        {

            for (j = 1; j <= n; ++j)

            {

                dis[i] = Min(dis[i], dis[j] + edge[j][i]);

            }

        }

    }

    printf ("%d ", dis[n]);

}

int main (void)

{

    while (scanf ("%d%d", &n, &m) && (m || n))

    {

        for (i = 0; i <= n; ++i)

        {

            for (j = 0; j <= n; ++j)

            {

                edge[i][j] = MAX;

            }

        }

        for (i = 0; i < m; ++i)

        {

            scanf ("%d%d%d", &start, &end, &value);

            edge[start][end] = edge[end][start] = value;

        }

        Bellman (1);

    }

    return 0;

}

3.SPFA算法

 一个Bellman-Ford算法优化: 每次只用距离减小的点去更新其他点

如何实现?队列!

 

思路:

 Step 1:初始时所有点d[]值置INF,源点d[]0。将源点放进队列。

Step 2:当队列不为空时每次从队列中取出队首,对队首的每条边进行松弛。将松弛后d[]值改变并且不在队列中的点加入队列

 

两点说明:

时间复杂度

最坏 : O(VE)一般 : O(kE)

如何判负环?

对每个点记录一个num值,表示被更新了多少次,如果某个点被更新的次数超过n-1次,则有负环

 

例题(1544)

Code:

#include <stdio.h>

#define MAX 1000000000

 

struct Edge

{

    int start;

    int end;

    int next;

    int value;

} eg[20005];

 

int m, n, i, pot;

int startNode, endNode, value;

int first, tail, popNumber;

int dis[105], head[105], queue[30000];

bool chose[200];

 

void Build (int st, int nd, int val)

{

    eg[pot].start = st;

    eg[pot].end = nd;

    eg[pot].value = val;

    eg[pot].next = head[st];

    head[st] = pot++;

}

 

void BFS (int x)

{

    int k;

    for (k = head[x]; k != -1; k = eg[k].next)

    {

        if (dis[eg[k].end] > dis[x] + eg[k].value)

        {

            dis[eg[k].end] = dis[x] + eg[k].value;

            if (chose[eg[k].end] == false)

            {

                queue[tail++] = eg[k].end;

                chose[eg[k].end] = true;

            }

        }

    }

}

 

void SPFA (void)

{

    dis[1] = 0;

    first = tail = 0;

    queue[tail++] = 1;

    //printf ("first = %d ", queue[first]);

    chose[1] = true;

    while (tail - first != 0)

    {

        //printf ("first = %d ", queue[first]);

        popNumber = queue[first];

        chose[queue[first]] = false;

        ++first;

        BFS (popNumber);

    }

    printf ("%d ", dis[n]);

}

 

int main (void)

{

    while (scanf ("%d%d", &n, &m) && (m || n))

    {

        for (i = 0; i <= n; ++i)

        {

            head[i] = -1;

            dis[i] = MAX;

            chose[i] = false;

        }

        pot = 0;

        for (i = 0; i < m; ++i)

        {

            scanf ("%d%d%d", &startNode, &endNode, &value);

            Build (startNode, endNode, value);

            Build (endNode, startNode, value);

        }

        SPFA ();

    }

    return 0;

}

4.Floyd算法

时间复杂度:  三重for循环  O(V^3)

 

先看代码:

for(k=1;k<=V;k++)

for(i=1;i<=V;i++)

for(j=1;j<=V;j++)

if(dis[i][j]>dis[i][k]+dis[k][j])

dis[i][j]=dis[i][k]+dis[k][j];    实际上是一个精巧的DP

DP过程:

dis[i][j][k]表示从ij的路径中,经过的点的编号不超过k的最短路

边界条件:dis[i][j][0] = dis[i][j]

转移方程:

dis[i][j][k] = Min(dis[i][j][k-1] , dis[i][k][k-1] + dis[k][j][k-1])

(k > 0 , 0 <= i , j <= n)

答案:dis[i][j][n]

 

例题(1544)

Code:

#include <stdio.h>

int i, j, k, m, n, start, end, value;

int map[200][200], dis[200][200];

const int MAX = 1000000000;

int Min (int a, int b)

{

    return a < b ? a : b;

}

int main (void)

{

    while (scanf("%d%d", &n, &m) && (m || n))

    {

        for (i = 0; i <= n; ++i)

        {

            for (j = 0; j <= n; ++j)

            {

                map[i][j] = MAX;

            }

        }

        for (i = 0; i < m; ++i)

        {

            scanf ("%d%d%d", &start, &end, &value);

            map[start][end] = map[end][start] = value;

        }

        for (k = 1; k <= n; ++k)

        {

            for (i = 1; i <= n; ++i)

            {

                for (j = 1; j <= n; ++j)

                {

                    map[i][j] = Min (map[i][j], map[i][k] + map[k][j]);

                }

            }

        }

        printf ("%d ", map[1][n]);

    }

    return 0;

}

 

<01>最短路算法的应用

求无向图最小环

最小环是指一个图中一个至少包含三个顶点的边权和最小的环

Floyd

设某环编号最大的顶点为 L 另两个顶点编号分别为 M N (M,N < L),则最大编号为 L 的最小环长度即为mp(M,L) + mp(N,L) + dp(M,N) ,其中 dp(M,N) 表示以 0L-1 号顶点为中间点时的最短路径,刚好符合 Floyd 算法最外层循环到 k=L 时的情况。

 

<02>若为有向图呢?(CDOJ 1329)

最短路算法的应用

求下面不等式组的一组解:

X1 - X2 <= 0 X1 - X5 <= -1 X2 - X5 <= 1 X3 - X1 <= 5 X4 - X1 <= 4 X4 - X3 <= -1 X5 - X3 <= -3 X5 - X4 <= -3

Xi<=0(i=1,2,3,4,5)

求完最短路后图中每条边

dis(v) <= dis(u) + w(u, v)

对于不等式Xi - Xj <= c,把它化成不等式:Xi <= Xj + c,就可以化成边Vj -> Vi,权值为c。最后,我们在这张图上求一次单源最短路径,这些不等式就会全部都满足

 

<03>最短路算法的应用

求下面不等式组的一组解:

X1 - X2 <= 0 X1 - X5 <= -1 X2 - X5 <= 1 X3 - X1 <= 5 X4 - X1 <= 4 X4 - X3 <= -1 X5 - X3 <= -3 X5 - X4 <= -3

Xi<=0(i=1,2,3,4,5)

对于最后一个Xi<=0怎么办?

新添一个X0=0,并使Xi-X0<=0!

最后以X0为源点,跑最短路

最后每个点的dis值就为答案

注意:由于有负边权,不能使用dijkstra

免责声明:文章转载自《最短路算法(小小总结一下)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Python——PYQT:控件基本使用一道面试题 vuex缺点?下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

windows命令行下批量拷贝同一后缀的文件到另外一个目录

一个目录下有许多文件夹,您希望将每个文件夹下的wmv文件复制到另一个目录。如果用鼠标打开一个文件,复制一个,然后打开另一个,一个一个操作起来非常麻烦。一段时间后,可以实现xcopy命令:例如,复制中的所有文件。Cdisk x1目录下的wmv格式到Ddisk x2:xcopyc:x1目录。wmv/sd:x2命令将x1下的子目录复制到x2。如果只想复制文件,则不...

grep多条件查找"与","或"

这里以jps命令为例jps查看全部的jvm进程"与"查找下图是所有jvm进程如果想查找256891ThriftServer服务用"与"查找可以理解为是条件查找命令:jps|grep-eer|grep-eT"或"查找方法一:grep-E'A|B'和grep-eA-eB方法二:egrep'A|B'方法三:awk'/A|B/'...

allure报告实现保存失败用例截图功能

allure中可以保存日志信息和截图日志allure能够自动识别。截图需要自己在添加allure方法。...

java--枚举

前言:Java中的enum也是一种类类型,它与一般类的区别在于1.世界上只有一个实例2.不能有公共构造函数3。您不能继承和继承枚举事例publicenumHttpCode{SUCCESS(200,“操作成功”)。//定义的每个枚举项都等效于通过构造函数HttpCode(int code,Stringmessage)实例化没有枚举项的通用HttpCo...

狼人杀规则

自爆后,所有演讲立即暂停,进入夜间。自爆后的那晚,狼人可以指着那把刀。预言家只能验证某个玩家是否是狼人,除狼人是否是狼人之外的所有信息都无法验证。如果先知测试丘比特,法官不必担心丘比特是哪一个阵营,只会展示好人的手势。...

5G中的频点计算及实例分析

相关图表:关于∏SSB的频域位置SSREF和GSCN之间的关系,请参见下表:注:SCSspacedchannelrasterisM=3的工作频带的默认值。同步网格是5G的第一个概念,旨在加快终端扫描SSB的频率位置。GSCN通常用于在SA联网模式下加速时频同步,以继续解释MIB和SIB1消息;对于NSA来说,这是不必要的。RRC重配置消息已经携带了NR的SS...