C#，加权有向无环图（DAG，Directed Acyclic Graph）的最长路径（Longest Path）算法与源程序

 

给定一个加权有向无环图（DAG）和其中的源顶点s，求出从s到给定图中所有其他顶点的最长距离。

一般图的最长路径问题不像最短路径问题那么容易，因为最长路径问题不具有最优子结构性质。事实上，对于一般图来说，最长路径问题是NP难问题。然而，对于有向无环图，最长路径问题具有线性时间解。该思想类似于有向无环图中最短路径的线性时间解。，我们使用拓扑排序。

我们将到所有顶点的距离初始化为负无穷大，到源的距离初始化为0，然后找到图的拓扑排序。图的拓扑排序表示图的线性排序（参见下文，图（b）是图（a）的线性表示）。一旦我们有了拓扑顺序（或线性表示），我们就会按照拓扑顺序逐个处理所有顶点。对于正在处理的每个顶点，我们使用当前顶点的距离更新其相邻顶点的距离。

 

最长路径问题是在地图中找到长度最大的简单路径的问题；换句话说，在图中所有可能的简单路径中，问题是找到最长的路径。对于未加权图，需要根据边的数量找到最长路径；对于加权图，必须使用边权重。为了解释开发该算法的过程，我们将首先开发一种用于计算无权有向无环图（DAG）的单源最长路径的算法，然后将其推广到计算DAG中的最长路径，无论是无权路径还是加权路径。我们已经了解了如何计算图中的单源最短路径cylicor acyclic-我们使用BFS计算未加权图的单源最短路径，并使用Dijkstra（仅限非负边权重）或Bellman Ford（允许负边权重）计算无负圈的加权图。如果我们需要所有对之间的最短路径，我们总是可以使用每个顶点作为源来运行单源最短路径算法；当然，弗洛伊德·沃沙尔已经做好了这样做的准备。最短路径问题具有最优子结构，这使得使用动态规划或贪婪算法成为可能——两个顶点之间最短路径中的子路径本身必须是最短的！然而，在寻找最长路径时，我们发现问题没有最优子结构，我们失去了使用动态规划的能力（当然还有贪婪策略！）。

最长路径算法的主要应用是在调度方面。假设我们有一个大项目，比如说，建造一座房子，它由许多小项目组成：挖掘地基、建造墙壁、连接煤气、电力和水、建造屋顶、进行室内装饰、美化环境等等。

其中一些活动需要在他们之前完成其他活动（你不能在建墙之前盖屋顶；你不想在挖水线之前进行景观美化），而其他活动可以同时完成（完成内部装饰和景观美化）。每个子作业都有完成它所需的预期时间；您想提前知道整个任务需要多长时间，以及何时应该完成各种子任务，以便您可以安排承包商。

从一系列这样的工作中，我们将构造一个加权的、有向的、非循环图。边将是子作业。每条边的权重将是作业的预期时间长度。

 

最长路径算法

现在，我们描述一种算法，用于查找从起始顶点S到所有其他顶点的最长路径。在某些方面，它类似于Dijkstra的算法，因为我们将保留一个“迄今为止发现的暂定最长路径”列表，并将其中一条到顶点v的路径迭代标记为实际最长路径，然后通过将到v的最长路径与v的边相结合，用可能新的最长路径更新我们的列表。

主要区别在于，将在开始时选择此更新的顺序——任何与有向图结构兼容的顶点顺序都将起作用。这些排序有时被称为“拓扑排序”。

拓扑排序

最长路径算法的第一步是对图的顶点进行编号/列出，以便所有边从较低的顶点流向较高的顶点。这样的列表称为顶点的“兼容总排序”，或顶点的“拓扑排序”。要存在这样一个列表，图必须是非循环的。否则，我们会问“先来的是什么，鸡还是蛋？”键入情况。例如，如果我们有一个有向循环a→B→C→A、 我们不能选择A、B、C中的任何一个放在第一位，因为每个顶点都有一个来自其他顶点的错误。

在我们运行的示例图中，顶点已经以与边结构兼容的方式进行了编号，因此已经进行了拓扑排序：S，1,2,3,4，F是满足所需属性的排序。

事实证明，这是唯一的障碍，只要图是非循环的，它就会有一个兼容的全序。用归纳法仔细地证明这一点并不太难，将证明转化为一个构造性的算法，转化为如何做到这一点，我们邀请您这样做。然而，在小图的实践中，通常不难找到总排序。从一个源（一个没有传入边、只有传出边的顶点）开始，然后继续查找只有来自列表中已存在顶点的传入边的顶点。

最后，我们应该强调顶点的拓扑排序通常不是唯一的。例如，在我们的运行示例中，2和3之间没有边，因此不是S，而是1,2,3,4，F

我们可以将顶点排序为S、1、3、2、4、F，这也是一个总排序。选择哪种总排序无关紧要——最长路径算法仍然有效。在实际应用中，有效的总排序通常是“显而易见的”。

参考：

C#，图（Graph）的数据结构设计与源代码https://blog.csdn.net/beijinghorn/article/details/125133711

源代码（POWER BY 315SOFT.COM）

using System;
using System.Collections;
using System.Collections.Generic;
 
namespace Legalsoft.Truffer.Algorithm
{
	public partial class Graph
	{
		private void Topological_Sort_Utility(int v, bool[] visited, Stack<int> stack)
		{
			visited[v] = true;
 
			for (int i = 0; i < Adjacency[v].Count; i++)
			{
				Edge e = FindEdge(v, Adjacency[v][i]);
				if (e == null) continue;
				if (!visited[e.Second])
				{
					Topological_Sort_Utility(e.Second, visited, stack);
				}
			}
			stack.Push(v);
		}
 
		public int[] Longest_Path(int s)
		{
			Stack<int> stack = new Stack<int>();
			int[] dist = new int[Node_Number];
 
			bool[] visited = new bool[Node_Number];
			for (int i = 0; i < Node_Number; i++)
			{
				visited[i] = false;
			}
			for (int i = 0; i < Node_Number; i++)
			{
				if (visited[i] == false)
				{
					Topological_Sort_Utility(i, visited, stack);
				}
			}
			for (int i = 0; i < Node_Number; i++)
			{
				dist[i] = int.MinValue;
			}
			dist[s] = 0;
 
			while (stack.Count > 0)
			{
				int u = stack.Peek();
				stack.Pop();
 
				if (dist[u] != int.MinValue)
				{
					for (int i = 0; i < Adjacency[u].Count; i++)
					{
						Edge e = FindEdge(u, Adjacency[u][i]);
						if (e == null) continue;
                        if (dist[e.Second] < dist[u] + e.Weight)
                        {
							dist[e.Second] = dist[u] + e.Weight;
						}
					}
				}
			}
			return dist;
		}
	}
 
	public static partial class GraphDrives
	{
		public static string Longest_Path()
		{
			Graph g = new Graph(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 s = 1;
			int[] dist = g.Longest_Path(s);
 
			return String.Join(",", dist);
		}
	}
}