单源最长路径问题不像单源最短路径问题那么简单，事实上，在大多图里，最长路径问题是 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

上述代码生成的图如下，

参考

• Longest Path in a Directed Acyclic Graph，GeeksforGeeks
• Longest path problem，维基百科

其它

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

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

(文章完)