给定一个加权有向无环图和图中的一个源顶点，求从给定源到所有其他顶点的最短路径。

对于一般的加权图，我们可以使用Bellman-Ford算法计算O（VE）时间内的单源最短距离。对于没有负权重的图，我们可以更好地使用Dijkstra算法计算O（E+VLogV）时间内的单源最短距离。对于有向无环图（DAG），我们能做得更好吗？我们可以计算DAG在O（V+E）时间内的单源最短距离。其思想是使用拓扑排序。

A DAG displays assumptions about the relationship between variables (often called nodes in the context of graphs). The assumptions we make take the form of lines (or edges) going from one node to another. These edges are directed, which means to say that they have a single arrowhead indicating their effect.

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

一、什么是有向无环图？

在进入DAGs之前，让我们先用图形的更广泛定义来设置基线。在这一点上，你可能已经知道了这一点，但它有助于为我们的意图和目的定义它，并为公平竞争创造条件。

图形只是节点或数据点的可视化表示，它们彼此之间有关系。当两个节点之间存在此关系时，它将创建称为边的对象。

DAG与其他图形的不同之处在于，它是只能在一个方向上流动的数据点的表示。我们能想到的最好的有向无环图示例是您的族谱。你奶奶生了你妈妈，然后妈妈生了你。但这种关系不能走另一条路。这在生物学上是不可能的。

这就是有向无环图的“有向”性质的形成原因。使它们非循环的原因是边缘之间没有其他关系。

这意味着，由于边之间的关系只能朝一个方向发展，因此数据点之间不存在“循环路径”。因此，它们是非循环的。

如何检查有向图是否是非循环的，一个很好的方法是查看是否有任何数据点可以相互“循环”。如果他们不能，那么你的图是非循环的。

如果有帮助，可以将DAG视为因果效应的图形表示。让我们回到我们的家谱示例。你的祖母是你母亲来这里的原因。你的母亲是你来这里的原因。看见你祖先中的每个成员之间的关系（如果我们将他们视为数据点）只能朝一个方向流动。

二、DAG属性

DAG是数据的唯一图形表示。因此，它们拥有自己独特的特性。这就是为什么在正确的实例中使用DAG时，DAG是如此有用的工具。

让我们更详细地了解DAG的属性。这样，您就可以更好地了解何时使用DAG可能会派上用场。

1、可达性

可达性是指图上两个节点之间相互可达的能力。想象一下，如果从给定节点开始，可以通过现有边“行走”到另一个节点。很简单吧？它取决于定义图形中数据点之间的关系。

当涉及到DAG时，发现可达性可能有点困难。无向图和有向图的可达性之间的主要区别是对称性。

在无向图中，可达性是对称的，这意味着每条边都是一条“双向街道”。换句话说，如果节点Y可以到达节点X，则节点X只能到达节点Y。

在有向图（如DAG）中，边是“单向街道”，可达性不必是对称的。

可达性还受到DAG是非循环的这一事实的影响。在非循环图中，可达性可以由偏序定义。偏序是一个集合中的一组较小的节点，它们仍然可以定义集合的整体关系。

这适用于DAG的地方是，偏序是反对称的。这意味着节点X可以到达节点Y，但节点Y不能到达节点X。回想一下族树。这基本上意味着你妈妈可以生你，但你不能生你妈妈。

这样，偏序有助于定义DAG的可达性。

2、传递闭包

图的传递闭包是另一个图，具有相同的节点集，其中每对可到达的节点之间都有一条直边。这意味着如果我们有一个有3个节点a、B和C的图，并且有一条边来自a->B，另一条边来自B->C，传递闭包也会有一条边来自a->C，因为C可以从a访问。

让我们以机场为例。如果图的每个节点都是一个机场，并且边表示有一个从机场到另一个机场的航班，则该图的传递闭包将添加通过中途停留可以到达的任何两个机场之间的直达航班。

3、传递约化

任何有向图的传递约简是具有尽可能少的边的相同节点的另一种图形表示。在许多方面，这与传递闭包相反。在这种情况下，传递性约简需要删除节点之间可通过其他路径访问的任何“冗余”边。

传递约简应该与原始图具有相同的可达性关系。它们还应该共享相同的传递闭包。

在DAG的情况下，传递约简将是一个具有最少可能边但保留与原始图相同的可达性关系的图。

4、拓扑排序

DAG的一个有用特性是节点可以按拓扑顺序排列。这意味着可以通过对图中的节点进行“排序”将其放入线性序列中。

如果我们回到我们的家谱示例，拓扑顺序将是几代。您的祖父母（作为节点）可以被安排到第1代。你的父母是第二代，你和你的兄弟姐妹是第三代，依此类推。

三、DAG的实际使用

现在您已经熟悉了DAG的概念，让我们把它弄明白。如果我们复习一些每天使用DAG的实际例子，可能会帮助您全面了解DAG。

1、机器学习

DAG对于机器学习很有用。如果你正在读这篇文章，这应该不会令人惊讶。为了让机器学习以前由人类完成的任务和过程，需要在计算机代码中列出这些协议。这就是DAG的用武之地。

在大多数情况下，神经网络的结构由DAG定义。这是许多AI和ML系统的“人工大脑”。

DAG的使用允许深入学习。这是因为DAG框架可以处理来自多个层的输入，以及提供多个层的输出。

2、加密货币/区块链

加密货币如今风靡一时。埃隆·马斯克喜欢在推特上谈论他们，并把他们带到月球上去。你可能听说过这些硬币依赖于所谓的区块链。

该区块链由一种名为Merkle树的东西定义，Merkle树是DAG的一种类型。这意味着，DAG也是金融业最大的转变之一。

3、零售

另一个使用DAG帮助其行业发展的领域是零售空间。零售业和其他行业都开始转向一种称为“客户旅程营销”的概念

这个想法是，没有人会立即做出购买的决定。客户必须经历一段“旅程”。零售商在整个过程中的多个地点使用广告，并介绍其产品。希望最终让他们的潜在客户购买。

零售商使用DAG将这些旅程地图可视化，并决定重点关注什么以改善其业务。

4、生物学

DAG存在于流行病学中，用于检测混杂因素。这些是可能影响研究的“意外变量”。

DAG的结构允许研究它的人将其用作视觉辅助。这使他们能够更轻松地讨论可能原因之间的潜在关系。对于具有非常复杂的变量的问题尤其如此。

5、版本控制

在Git或其他源代码管理方法中提交对构建的更改时，用于跟踪更改的底层结构是DAG（类似于区块链的Merkle树）。对这些更改如何应用进行可视化可以有所帮助。每个节点包含更改，每个边表示状态之间的关系（此更改发生在其他更改之后）。

使用DAG有助于确保团队可以在相同的代码库上工作，而无需互相干涉，同时能够将其他人引入到他们自己的项目中的更改添加进来。同样的原则也适用于数据版本控制。

6、行程安排

在计算机科学中，您可以使用DAG来确保计算机知道何时可以获得输入。您可以使用DAG作为一组指令来通知程序应如何安排进程。

如果程序的一部分需要另一部分尚未生成的输入，则可能是一个问题。因此，这将以正确的顺序优先考虑正确的流程。

7、数据管道–Apache Airflow

Apache Airflow是数据科学领域中调度用例的一个示例。Airflow和其他调度工具允许创建工作流图，工作流图是用于调度数据处理的DAG。这些用于确保以正确的顺序处理数据。

四、源程序

1、参考代码

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

2、核心程序

using System;using System.Collections;using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm{public partial class Graph{private List AjointNodes(int node){List list = new List();foreach (Edge edge in Edges){if (edge.First == node){list.Add(new Edge(edge.First, edge.Second, edge.Weight));}else if (edge.Second == node){list.Add(new Edge(edge.Second, edge.First, edge.Weight));}}return list;}public void Topological_Sort_Utility(int v, bool[] visited, ref Stack stack){visited[v] = true;List adj = AjointNodes(v);foreach (Edge edge in adj){if (visited[edge.Second] == false){Topological_Sort_Utility(edge.Second, visited, ref stack);}}stack.Push(v);}public int[] Shortest_Path_From(int s){Stack stack = new Stack();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, ref stack);}}for (int i = 0; i < Node_Number; i++){dist[i] = int.MaxValue;}dist[s] = 0;while (stack.Count != 0){int u = (int)stack.Pop();if (dist[u] != int.MaxValue){List adj = AjointNodes(u);foreach (Edge edge in adj){if (dist[edge.Second] > dist[u] + edge.Weight){dist[edge.Second] = dist[u] + edge.Weight;}}}}return dist;}}public static partial class GraphDrives{public static string ShortestPath(){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, 4, -1);g.AddEdge(4, 5, -2);int s = 1;return String.Join(",", g.Shortest_Path_From(s));}}}