单源最长路径问题不像单源最短路径问题那么简单,事实上,在大多图里,最长路径问题是 NP 问题。但是对于有向无环图(DAG,即 Directed Acyclic Graph)来说,最长路还是可以求解的,因此本篇文章主要来看看 DAG 下最长路径是如何求解的。

有两种解决方案:

  1. 使用 Bellman-Ford 或者 SPFA 算法。将所有的边权变为它的相反数,然后求最短路。求出之后,取单源最短路结果的相反数,就可以得到单源最长路。
  2. 使用拓扑排序序列。

第一个方法比较简单,我之前的文章有讲过这两个算法,因此就不作过多介绍了(需要注意,这里不能用 Dijkstra,因为它不能用于负权图)。在进行第二种方法讲解之前,请先了解下何谓拓扑排序

问题及分析

我们先定义下问题,给定一个 DAG(即有向无环图),和一个源点 source,其中图有 n 个点 m 条边。求 source 到其它所有点的最长路径;如果不存在路径,输出 INF。

处理思路如下:

  1. 初始化 dist[] 为最小值,其中 dist[source] = 0
  2. 生成 DAG 的拓扑序列
  3. 按照拓扑序列的每个顶点 u,依次进行以下步骤
    3.1. 遍历 u 的每个邻接顶点 v
    3.2. if (dist[v] < dist[u] + weight(u, v)),则 dist[v] = dist[u] + weight(u, v)

代码实现

#include <iostream>
#include <list>
#include <queue>

using namespace std;

struct Edge
{
    int v;
    int weight;

    Edge(int _v, int _weight)
    {
        v = _v;
        weight = _weight;
    }
};

class Graph
{
public:

    Graph(int vertexNumber);
    ~Graph();

    // 添加边
    void addEdge(int u, int v, int weight);

    // 求出最长路径
    void longestPath(int source);

private:

    // 求出拓扑排序序列
    queue<int> topologicalSort();

private:

    int         m_vertexNumber; // 顶点数目
    int*        m_inDegree;     // 入度
    list<Edge>* m_adjList;      // 邻接表

};

Graph::Graph(int vertexNumber)
{
    m_vertexNumber = vertexNumber;
    m_adjList = new list<Edge>[m_vertexNumber];
    m_inDegree = new int[m_vertexNumber];

    for (int i = 0; i < m_vertexNumber; ++i)
        m_inDegree[i] = 0;
}

Graph::~Graph()
{
    delete[] m_adjList;
    delete[] m_inDegree;
}

void Graph::addEdge(int u, int v, int weight)
{
    Edge e(v, weight);
    m_adjList[u].push_back(e);
    m_inDegree[v]++;
}

queue<int> Graph::topologicalSort()
{
    queue<int> qRet; // 存储拓扑序列,作为返回值
    queue<int> q;    // 用作拓扑排序过程

    // 找到所有入度为 0 的顶点,并入队列
    for (int i = 0; i < m_vertexNumber; ++i)
    {
        if (m_inDegree[i] == 0)
        {
            m_inDegree[i]--;
            q.push(i);
            qRet.push(i);
        }
    }

    while (q.empty() == false)
    {
        int u = q.front();
        q.pop();

        list<Edge>::iterator it;
        for (it = m_adjList[u].begin(); it != m_adjList[u].end(); ++it)
        {
            int v = it->v;
            m_inDegree[v]--;
            if (m_inDegree[v] == 0)
            {
                q.push(v);
                qRet.push(v);
            }
        }
    }

    return qRet;
}

void Graph::longestPath(int source)
{
    // 存储源点到每个点的最长路径
    int* dist = new int[m_vertexNumber];
    for (int i = 0; i < m_vertexNumber; ++i)
        dist[i] = INT_MIN;

    // 源点到源点的最长路径为 0
    dist[source] = 0;

    // 求出拓扑排序
    queue<int> q = topologicalSort();

    // 最长路径求解
    while (q.empty() == false)
    {
        int u = q.front();
        q.pop();

        list<Edge>::iterator it;
        if (dist[u] != INT_MIN)
        {
            for (it = m_adjList[u].begin(); it != m_adjList[u].end(); ++it)
            {
                if (dist[it->v] < dist[u] + it->weight)
                    dist[it->v] = dist[u] + it->weight;
            }
        }
    }
    
    // 输出最长路径
    for (int i = 0; i < m_vertexNumber; ++i)
        (dist[i] == INT_MIN) ? cout << "INF " : cout << dist[i] << " ";

    delete[] dist;
}

int main()
{
    Graph g(6);
    g.addEdge(0, 1, 5);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 3, 6);
    g.addEdge(1, 2, 2);
    g.addEdge(2, 4, 4);
    g.addEdge(2, 5, 2);
    g.addEdge(2, 3, 7);
    g.addEdge(3, 5, 1);
    g.addEdge(3, 4, -1);
    g.addEdge(4, 5, -2);

    int source = 1;
    g.longestPath(source);

    return 0;
}

运行测试如下,

INF 0 2 9 8 10

上述代码生成的图如下,

参考

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2020-06-27
原文链接:https://ethsonliu.com/2020/06/longest-path-problem.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。