单源最长路径
单源最长路径问题不像单源最短路径问题那么简单,事实上,在大多图里,最长路径问题是 NP 问题。但是对于有向无环图(DAG,即 Directed Acyclic Graph)来说,最长路还是可以求解的,因此本篇文章主要来看看 DAG 下最长路径是如何求解的。
有两种解决方案:
- 使用 Bellman-Ford 或者 SPFA 算法。将所有的边权变为它的相反数,然后求最短路。求出之后,取单源最短路结果的相反数,就可以得到单源最长路。
- 使用拓扑排序序列。
第一个方法比较简单,我之前的文章有讲过这两个算法,因此就不作过多介绍了(需要注意,这里不能用 Dijkstra,因为它不能用于负权图)。在进行第二种方法讲解之前,请先了解下何谓拓扑排序。
问题及分析
我们先定义下问题,给定一个 DAG(即有向无环图),和一个源点 source,其中图有 n 个点 m 条边。求 source 到其它所有点的最长路径;如果不存在路径,输出 INF。
处理思路如下:
- 初始化
dist[]
为最小值,其中dist[source] = 0
- 生成 DAG 的拓扑序列
- 按照拓扑序列的每个顶点
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,谢谢。
(文章完)
文章作者:刘毅 (Ethson Liu)
发布日期:2020-06-27
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。