算法整理（三）图中的路径问题

96 阅读 0 评论 64 点赞

我是靠谱客的博主坦率薯片，这篇文章主要介绍算法整理（三）图中的路径问题，现在分享给大家，希望可以做个参考。

单源最短路

BFS

如果图中没有权值，直接用BFS就可以解决

Dijkstra算法

又称迪杰斯特拉算法，是一个经典的最短路径算法，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止，使用了广度优先搜索解决赋权有向图的单源最短路径问题，算法最终得到一个最短路径树。时间复杂度为O(N^2)

①先取一点v[0]作为起始点，初始化dis[i],d[i]的值为v[0]到其余点v[i]的距离w0，如果直接相邻初始化为权值，否则初始化为无限大；

②将v[0]标记，vis[0] = 1(vis一开始初始化为0)；

③找寻与v[0]相邻的最近点v[k]，将v[k]点记录下来，v[k]与v[0]的距离记为min；

④把v[k]标记，vis[k]=1；

⑤查询并比较，让dis[j]与min+wk进行比较，判断是直接v[0]连接v[j]短，还是经过v[k]连接v[j]更短，即dis[j]=MIN(dis[j],min+wk)；

⑥继续重复步骤③与步骤⑤，知道找出所有点为止。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int dijkstra(int n)
{
    //初始化v[0]到v[i]的距离
    for(int i=1;i<=n;i++)
        dis[i] = w[0][i];
    vis[0]=1;//标记v[0]点
    for(int i = 1; i <= n; i++)
    {
        //查找最近点
        int min = INF,k = 0;
        for(int j = 0; j <= n; j++)
            if(!vis[j] && dis[j] < min)
                min = dis[j],k = j;
        vis[k] = 1;//标记查找到的最近点
        //判断是直接v[0]连接v[j]短，还是经过v[k]连接v[j]更短
        for(int j = 1; j <= n; j++)
            if(!vis[j] && min+w[k][j] < dis[j])
                d[j] = min+w[k][j];
    } 
    return dis[j];
}

时间复杂度：
这里写图片描述

Bellman-Ford算法

Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).
以下操作循环执行至多n-1次，n为顶点数：
对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；
为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

复制代码

#include <iostream>
using namespace std;
const int maxnum = 100;
const int maxint = 99999;

// 边，
typedef struct Edge{
    int u, v;    // 起点，重点
    int weight;  // 边的权值
}Edge;

Edge edge[maxnum];     // 保存边的值
int  dist[maxnum];     // 结点到源点最小距离

int nodenum, edgenum, source;    // 结点数，边数，源点

// 初始化图
void init()
{
    // 输入结点数，边数，源点
    cin >> nodenum >> edgenum >> source;
    for(int i=1; i<=nodenum; ++i)
        dist[i] = maxint;
    dist[source] = 0;
    for(int i=1; i<=edgenum; ++i)
    {
        cin >> edge[i].u >> edge[i].v >> edge[i].weight;
        if(edge[i].u == source)          //注意这里设置初始情况
            dist[edge[i].v] = edge[i].weight;
    }
}

// 松弛计算
void relax(int u, int v, int weight)
{
    if(dist[v] > dist[u] + weight)
        dist[v] = dist[u] + weight;
}

bool Bellman_Ford()
{
    for(int i=1; i<=nodenum-1; ++i)
        for(int j=1; j<=edgenum; ++j)
            relax(edge[j].u, edge[j].v, edge[j].weight);
    bool flag = 1;
    // 判断是否有负环路
    for(int i=1; i<=edgenum; ++i)
        if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
        {
            flag = 0;
            break;
        }
    return flag;
}
int main()
{
    //freopen("input3.txt", "r", stdin);
    init();
    if(Bellman_Ford())
        for(int i = 1 ;i <= nodenum; i++)
            cout << dist[i] << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
using namespace std;
const int maxnum = 100;
const int maxint = 99999;

// 边，
typedef struct Edge{
    int u, v;    // 起点，重点
    int weight;  // 边的权值
}Edge;

Edge edge[maxnum];     // 保存边的值
int  dist[maxnum];     // 结点到源点最小距离

int nodenum, edgenum, source;    // 结点数，边数，源点

// 初始化图
void init()
{
    // 输入结点数，边数，源点
    cin >> nodenum >> edgenum >> source;
    for(int i=1; i<=nodenum; ++i)
        dist[i] = maxint;
    dist[source] = 0;
    for(int i=1; i<=edgenum; ++i)
    {
        cin >> edge[i].u >> edge[i].v >> edge[i].weight;
        if(edge[i].u == source)          //注意这里设置初始情况
            dist[edge[i].v] = edge[i].weight;
    }
}

// 松弛计算
void relax(int u, int v, int weight)
{
    if(dist[v] > dist[u] + weight)
        dist[v] = dist[u] + weight;
}

bool Bellman_Ford()
{
    for(int i=1; i<=nodenum-1; ++i)
        for(int j=1; j<=edgenum; ++j)
            relax(edge[j].u, edge[j].v, edge[j].weight);
    bool flag = 1;
    // 判断是否有负环路
    for(int i=1; i<=edgenum; ++i)
        if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
        {
            flag = 0;
            break;
        }
    return flag;
}
int main()
{
    //freopen("input3.txt", "r", stdin);
    init();
    if(Bellman_Ford())
        for(int i = 1 ;i <= nodenum; i++)
            cout << dist[i] << endl;
    return 0;
}

与迪科斯彻算法不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路，用于有向无环图的最短路径算法对每条边仅松弛一次。Bellman-Ford“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。

每次松弛操作实际上是对相邻节点的访问，第n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过V-1条边，所以可知贝尔曼-福特算法所得为最短路径。

队列优化：
求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。复杂度可以降低到O(kE)，k是个比较小的系数(并且在绝大多数的图中，k<=2，然而在一些精心构造的图中可能会上升到很高)

实现方法：建立一个队列，初始时里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空
判断有无负环：如果某个点进入队列的次数超过N次则存在负环 (存在负环则无最短路径，如果有负环则会无限松弛，而一个带n个点的图至多松弛n-1次。

多源最短路

Floyd算法

可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包

先将边的距离初始化为直接到达的距离，有就是权值，没有就是无穷大。然后借助1节点中转，得到的距离就是通过1和不通过1直接到达的距离最小值。接着借助2中转，依次循环下去。

复制代码

1
2
3
4
5
for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(e[i][j]>e[i][k]+e[k][j])
                 e[i][j]=e[i][k]+e[k][j];