最小生成树（prime算法、kruskal算法）最短路径算法（Floyd,bellmen-ford,dijkstra,Spfa)

Tang7O

发布于：2020年4月10日

字数统计: 4.1k字 | 阅读时长: 18分

1 最小生成树

生成树的概念：联通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树生成树是联通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之编程非连通图。生成树各边的权值总和称为生成素的权。权最小的生成树称为最小生成树，常用的算法有prime算法和kruskal算法。
举例：几个村庄都不相通, 要修路, 怎么修, 这个花的钱最少, 这种最优选择就是最小生成树

1.1例题

为了便于理解，所以有了这个例题题目链接

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

Output

对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

Sample Input

3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100

Sample Output

3
?

1.2 Prime算法

Prime算法的基本思想

清空生成树，任取一个顶点加入生成树。
在那些一个端点在生成树里，另一个端点不在生成树里的边中，选取一条权最小的边，将它和另一个端点加进生成树。
重复步骤2，直到所有的顶点都进入了生成树为止，此时的生成树就是最小生成树。

结合上面的例题来介绍具体算法实现
AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define mem(a, b) memset(a, b, sizeof(a))
#define PI 3.1415926535
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f; 
const long long LLINF = 0x3f3f3f3f3f3f3f3f;
const int MAXn = 100;
const int mod = 1;

int map[MAXn][MAXn];  //存图 map[i][j]==p 表示从i到j的距离为p
bool Is_Used[MAXn];  //Is-Used[i]=true 表示点i已经在最小生成树中
int Low_Cost[MAXn];  //Low_Cost[i] 表示最小生成树中的所有点到i点的距离的最小值
int main()
{
    int n, m; 
    while (cin >> n >> m)
    {
        if (n == 0)
            break;
        mem(map,INF);
        int i, a, b, c, ans = 0, ok = 1;
        for (i = 1; i <= n; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            map[a][b]=map[b][a] =c;
        }
        mem(Is_Used, 0); //将Is_Used数组清零
        Is_Used[1] = true; // 将V1（第一个点）存入树中作为起点
        for (i = 1; i <= m; i++)//因为最小生成树中只有V1 所以Low_Cost[i]=map[1][i]
            Low_Cost[i] = map[1][i];
        for (i = 2; i <= m; i++)
        {//遍历其他的点（不在最小生成树中的点
            int Min = INF, New_Point = -1;
            for (int j = 1; j <= m; j++)
            {//找不在最小生成树中的点到最小生成树中的点的最小距离，存为新的点
                if (!Is_Used[j] && Min > Low_Cost[j])
                {
                    Min = Low_Cost[j];
                    New_Point = j;
                }
            }
            Is_Used[New_Point] = true;//将新的点入树
            ans += Min;
            for (int j = 1; j <= m; j++)
            {//更新不在最小生成树中的点到最小生成树中的点的最小距离
                if (!Is_Used[j])
                    Low_Cost[j] = min(Low_Cost[j], map[New_Point][j]);
            }
        }
        for (i = 1; i <= m; i++)
        {//判断是否所有点都已入树
            if (!Is_Used[i])
            {
                ok = 0;
                break;
            }
        }
        if (ok)
            printf("%d\n",ans);
        else
            printf("?\n");
    }
    return 0;
}

1.3 Kruskal算法

Kruskal算法 ：构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树的根节点，则它是一个含有n棵树的森林。之后，从网的边集中选取一条权值最小的边，若该边的两个顶点分属不同的树，则将其加入子图，也就是这两个顶点分别所在的两棵树合成一棵树；反之，若该边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林只有一棵树。kruskal算法能够在并查集的基础很快的实现。并查集参考：并查集结合上面的例题来介绍具体算法实现
AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define mem(a, b) memset(a, b, sizeof(a))
#define PI 3.1415926535
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const long long LLINF = 0x3f3f3f3f3f3f3f3f;
const int MAXn = 105;
const int mod = 1;

struct egde
{     //u到v的距离为w
    int u,v;
    int w;
}s[MAXn*MAXn];
int pre[MAXn];//并查集数组
bool cmp(egde a,egde b)
{
    return a.w<b.w;
}
int Find(int a)
{
    int root=a;
    int tem;
    while(root!=pre[root])
        root=pre[root]; //找老大（祖先
    while(a!=root)
    {  //路径压缩
        tem=a;  
        a=pre[a]; 
        pre[a]=root;
    }
    return root;
}

void kruskal(int n,int m)
{
    int ans=0,i,ok=1;
    for(i=0;i<n;i++)
    { //从权最小的边开始加进图中 
        int x=Find(s[i].u);
        int y=Find(s[i].v);
        if(x!=y)
        { 
            if(x>y)
                swap(x,y);
            pre[x]=y; 
            ans+=s[i].w;
        }
    }
    for(i=1;i<=m;i++)
    {//判断是否所有点都已入树
        if(Find(i)!=Find(1))
        {
            ok=0;
            break;
        }
    }
    if(ok)
        printf("%d\n",ans);
    else
        printf("?\n");
}
int main()
{
    int n,m;
    while (~scanf("%d%d",&n,&m))
    {
        if (n == 0)
            break;
        mem(s,0);
        for(int i=0;i<=MAXn;i++)
            pre[i]=i; //初始化
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&s[i].u,&s[i].v,&s[i].w);
        }
        sort(s,s+n,cmp); //对边按权从小到大排序 
        kruskal(n,m);
    }
    return 0;
}

2 最短路径

最短路径问题旨在寻找图中两节点之间的最短路径

2.1 例题

题目链接

Problem Description

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

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

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

Sample Input
2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

0 0

Sample Output
3

2.2 Floyd算法

Floyd算法求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。 Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。
Floyd-Warshall的原理是动态规划：设Di,j,k为从i到j的只以(1…k)集合中的节点为中间节点的最短路径的长度。若最短路径经过点k，则Di,j,k = Di,k,k-1 + Dk,j,k-1；若最短路径不经过点k，则Di,j,k = Di,j,k-1。因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。

for(i=0;i<=m;i++)
    for(j=0;j<=n;j++)
        map[i][j]=INF;//初始化 
for(k=1;k<=n;k++)//动态规划的思想  
    for(i=1;i<=n;i++)  
        for(j=1;j<=n;j++)  
        {  
            if(i==j)  
                continue;  
            if(map[i][j]>map[i][k]+map[k][j])  
                map[i][j]=map[i][k]+map[k][j];  
        }

结合上面的例题来介绍具体算法实现

AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define mem(a, b) memset(a, b, sizeof(a))
#define PI 3.1415926535
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const long long LLF = 0x3f3f3f3f3f3f3f3f;
const int MAXn = 105;
const int mod = 1;

int n, m;
int w[MAXn][MAXn]; //a->b的距离

void Floyd()
{
    int k, i, j;
    for (k = 1; k <= n; k++) //中间点
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
}

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        if (!n && !m)
            break;
        int i, j, a, b, c;
        for (i = 0; i <= n; i++)
            for (j = 0; j <= n; j++)
            { //初始化
                w[i][j] = (i == j ? 0 : INF);
            }
        for (i = 0; i < m; i++)
        { //输入
            scanf("%d%d%d", &a, &b, &c);
            w[a][b] = min(w[a][b], c);
            w[b][a] = w[a][b];
        }
        Floyd(); //Floyd算法求最短路径
        printf("%d\n", w[1][n]);//输出起到点n的最短路径
    }
    return 0;
}

2.3 Dijkstra算法

Dijkstra算法求单源、无负权的最短路。时效性较好，时间复杂度为O（V* V+E）。

源点可达的话，O（V* lgV+E* lgV）=>O（E* lgV）。

当是稀疏图的情况时，此时E=V* V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V* lgV + E）。

算法流程：
(a) 初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞；
(b) 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径；
(c ) 修改最短路径：计算u的邻接点的最短路径，若(v,…,u)+(u,w)<(v,…,w)，则以(v,…,u,w)代替。
(d) 重复(b)-(c )，直到求得v到其余所有顶点的最短路径。
特点：总是按照从小到大的顺序求得最短路径。

假设一共有N个节点，出发结点为s，需要一个一维数组vis[N]来记录前一个节点序号，一个一维数组dis[N]来记录从原点到当前节点最短路径（初始值为s到Vi的边的权值，没有则为+∞），一个二维数组map[N][N]来记录各点之间边的权重，按以上流程更新map[N]和dis[N]。

void dijs(int v)//v为原点   
{  
    int i,j,k;  
    for(i=1;i<=n;i++)  
    dis[i]=map[v][i];//初始化   
    memset(vis,0,sizeof(vis));  
    vis[v]=1;  
    for(i=2;i<=n;i++)  
    {  
        int min=INF;  
        k=v;  
        for(j=1;j<=n;j++)  
        {  
            if(!vis[j]&&min>dis[j])  
            {  
                k=j;  
                min=dis[j];//在dis中找出最小值   
             }   
        }  
        vis[k]=1;//使k为已生成终点   
        for(j=1;j<=n;j++)//修改dis   
        {  
            if(dis[j]>dis[k]+map[k][j])  
            dis[j]=dis[k]+map[k][j];  
        }  
    }  
}

结合上面的例题来介绍具体算法实现
AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define mem(a, b) memset(a, b, sizeof(a))
#define PI 3.1415926535
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const long long LLINF = 0x3f3f3f3f3f3f3f3f;
const int MAXn = 105;
const int mod = 1;

int n, m;
int w[MAXn][MAXn]; //a->b的距离
bool v[MAXn];      //标记数组
int d[MAXn];       //起点到点i的最小距离

void Dijkstra(int s)//起点是s
{ 
    int i, j;
    for (i = 1; i <= n; i++)
        d[i] = w[s][i]; //存储距离
    mem(v, 0); //标记数组清零
    v[s]=true;  //标记
    for (i = 1; i < n; i++) //遍历n-1遍（其他的点
    {
        int m = -1, Min = INF;
        for (j = 1; j <= n; j++)
        { //寻找到当前点距离最近的点
            if (!v[j] && d[j] < Min)
                Min = d[m = j];
        }
        v[m]=true; //将刚找到的点标记
        for (j = 1; j <= n; j++)
        { //更新最小距离
            d[j] = min(d[j], d[m] + w[m][j]);
        }
    }
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        if (!n && !m)
            break;
        int i, j, a, b, c;
        for (i = 0; i <= n; i++)
            for (j = 0; j <= n; j++)
            { //初始化 
                w[i][j] = (i == j ? 0 : INF);
            }
        for (i = 0; i < m; i++)
        { 
            scanf("%d%d%d", &a, &b, &c);
            w[a][b] = min(w[a][b], c);
            w[b][a] = w[a][b];
        }
        Dijkstra(1); //Dijkstra算法求最短路径
        printf("%d\n", d[n]);//输出起点到点n的最小距离
    }
    return 0;
}

2.4 Bellman-Ford算法

适用条件&范围：

单源最短路径(从源点s到其它所有顶点v);
有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
边权可正可负(如有负权回路输出错误提示);
差分约束系统;

Bellman－Ford算法可以大致分为三个部分

第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况: d（v） > d (u) + w(u,v)，如果存在则返回false，表示途中存在从源点可达的权为负的回路。

之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则应为无法收敛而导致不能求出最短路径。

bool bellman()  
{  
    bool flag ;  
    for(int i=0;i<n-1;i++)  
    {  
        flag=false;  
        for(int j=0;j<all;j++) //穷举每条边 
            if(dis[t[j].to]>dis[t[j].from]+t[j].vis) //松弛判断 
            {  
                dis[t[j].to]=dis[t[j].from]+t[j].vis;  //松弛操作 
                flag=true;  
            }  
            if(!flag)  
                break;  
    }  
    for(int k=0;k<all;k++) //对所有边进行一次遍历，判断是否有负回路 
        if(dis[t[k].to]>dis[t[k].from]+t[k].vis)  
            return true;  
    return false;  
}

2.5 SPFA算法

SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。
SPFA算法可以用于存在负数边权的图
SPFA算法是Bellman-Ford算法的一种优化，大大降低了时间复杂度。结合上面的例题来介绍具体算法实现
AC代码：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#define mem(a, b) memset(a, b, sizeof(a))
#define PI 3.1415926535
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const long long LLF = 0x3f3f3f3f3f3f3f3f;
const int MAXn = 105;
const int mod = 1;

int n, m;
int w[MAXn][MAXn]; //a->b的距离
bool v[MAXn];      //标记
int d[MAXn];       //d[i] 起始位置到i的最小距离

void Spfa(int s)//起始位置
{
    int i, j;
    mem(v, 0);
    for(i=0;i<=n;i++)
        d[i]=INF; //初始化
    d[s]=0; // 重要
    queue<int> q; 
    q.push(s); //入队
    v[s]=true; //标记
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        v[now]=false; //重要
        for(i=1;i<=n;i++)
        {
            if(d[i]>d[now]+w[now][i])
            { //更新最短距离
                d[i]=d[now]+w[now][i];
                if(v[i]==0)
                {
                    v[i]=true;
                    q.push(i);
                }
            }
        }
    }
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        if (!n && !m)
            break;
        int i, j, a, b, c;
        for (i = 0; i <= n; i++)
            for (j = 0; j <= n; j++)
            { //初始化
                w[i][j] = (i == j ? 0 : INF);
            }
        for (i = 0; i < m; i++)
        { //输入
            scanf("%d%d%d", &a, &b, &c);
            w[a][b] = min(w[a][b], c);
            w[b][a] = w[a][b];
        }
        Spfa(1);//Spfa算法求最短路径
        printf("%d\n", d[n]); //输出起到点n的最短路径
    }
    return 0;
}

更新于：2022年4月13日

题目

算法

RMQ算法详解（在线ST）

1. 概述 RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返...

MarkDown-改变字体颜色大小

转自 testcs_dn(微wx笑) 博文 –>传送门 123456<font face="黑体">我是黑体字</font><font f...

最小生成树（prime算法、kruskal算法） 最短路径算法（Floyd,bellmen-ford,dijkstra,Spfa)