DAG，Dijkstra算法,Bellmen-ford算法的原理、异同、应用
DAG，Dijkstra算法,Bellmen-ford算法的原理、异同、应用
一、DAG(有向无环图)
（一）原理
DAG(有向无环图)是一种特殊的图结构。它由顶点和有向边组成，并且不存在任何环,即从一个顶点出发沿着有向边无法回到该顶点自身。
（二）应用
1.拓扑排序
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
（1）每个顶点出现且只出现一次。
（2）若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
2.求最短路径
（1）初始化
首先对DAG图进行拓扑排序，得到顶点的线性序列v1,v2,...vn。设源点为S,创建一个距离数组dist[s]=0,初始化dist[s]=0,对于其他顶点v(v≠s)，dist[v]=∞(表示初始到这些顶点的距离为无穷大)。
（2）按拓扑序列更新距离
按照拓扑排序的顺序依次处理每个顶点vi。对于vi的每个出边(vi,vj)，边的权重为w(vi,vj)，如果dist[vi]+w(vi,vj)<dist[vj]，则更新dist[vj]=dist[vi]+w(vi,vj)。这是因为在拓扑排序中，vi在vj之前，当处理到vi时，dist[vi]已经是从源点到vi的最短距离。经过上述步骤后，数组中存储的就是源点到各个顶点的最短路径。
二、Dijkstra算法
（一）原理
Dijkstra 算法用于计算带非负权重的有向图或无向图中一个源节点到其他所有节点的最短路径。算法维护一个集合S，初始时S只包含源节点。同时维护一个距离数组dist[]，用于记录源节点到其他节点的当前最短距离估计值。在每次迭代中，从不在中S的节点中选择距离源节点最短距离估计值最小的节点u，将其加入S。然后，对于u的所有邻接节点v，更新dist[v]的值为min(dist[v],dist[u]+w(u,v))，其中w(u,v)是边(u,v)的权重。重复这个过程直到所有节点都在S中。
（二）应用
1.求最短路径
初始：若从v0开始，令final[0]=true，dist[0]=0，path[0]=-1。其余顶点final[k]=false，dist[k]=arcs[0][k]，path[k]=(arcs[0][k]==∞）？-1：0。
n-1轮处理：循环遍历所有顶点，找到还没确定最短路径，且dist最小的顶点vi,令final[i]=ture。并邻接自vi的顶点，对于邻接自vi的顶点vj，若final[j]==false且dist[i]+arcs[i][j]<dist[j]，则令dist[j]=dist[i]+arcs[i][j]，path[j]=i。(arcs[i][j]表示vi到vj的弧的权值)
2.实际应用（根据最短路径）
（1）网络路由：在计算机网络中，计算从源路由器到其他路由器的最短路径，以优化数据传输路径。例如，在互联网中，确定数据包从源主机到目标主机的最优传输路径。
（2）物流配送：寻找配送中心到各个客户点的最短路径，以降低运输成本和时间。
（3）游戏开发：计算游戏角色从起始位置到目标位置的最短移动路径，例如在即时战略游戏或角色扮演游戏中。
三、Bellmen-ford算法
（一）原理
Bellman - ford 算法用于计算带权重（可以为负权重）的有向图中一个源节点到其他所有节点的最短路径。算法的核心思想是进行v-1次松弛操作，其中v是图中的节点数。松弛操作是指对于每条边(u,v)，如果dist[u]+w(u,v)<dist[v]，则更新dist[v]=dist[u]+w(u,v)。在v-1次松弛操作之后，再进行一次遍历所有边的检查，如果仍然可以对某条边进行松弛操作，那么说明图中存在负权回路。
（二）应用
1.求最短路径
假设有一个有向图G=(V，E)，其中V={1,2,3,4}，E={(1,2,-1)，(1,3,4)，(2,3,3)，(2,4,2)，(3,4，-3)}(这里(u，v，w)表示从顶点u到顶点v的边，权重为w)，源点s=1。
初始化:
dist[1]=0,dist[2]=∞,dist[3]=∞,dist[4]=∞。
第一次松弛操作(共3次，这里V=4)：
对于边(1,2，-1)：因为dist[1]+(-1)=0-1=-1<dist[2]=∞，所以dist[2]=-1。
对于边(1,3,4)：因为dist[1]+4=0+4=4<dist[3]=∞，所以dist[3]=4。
第二次松弛操作:
对于边(2,3,3)：因为dist[2]+3=-1+3=2<dist[3]=4，所以dist[3]=2。
对于边(2,4,2)：因为dist[2]+2=-1+2=1<dist[4]=∞，所以dist[4]=1。
第三次松弛操作:
对于边(3,4，-3)：因为dist[3]+(-3)=2-3=-1<dist[4]=1，所以dist[4]=-1.
检测负权回路：
再次遍历所有边进行松弛操作，发现没有边能再进行松弛操作，所以得到从源点1到顶点2的最短路径长度为-1，到顶点3为2，到顶点4为-1。
2.实际应用
（1）金融分析：在金融市场中，存在汇率波动(可视为负权重情况)，可以用 Bellman - ford 算法计算货币兑换中的最优汇率路径。
（2）动态系统建模：在一些动态系统中，状态转移成本可能为负，例如在某些资源分配问题中，回收资源可能会带来负的成本，此时可以使用 Bellman - ford 算法来寻找最优的状态转移路径。
四、三者异同点
1.相同点
三者都是用于解决图中的最短路径问题。
2.不同点
（1）权重限制：Dijkstra 算法要求边权重非负，而 Bellman - ford 算法可以处理负权重边。DAG 对边权重没有特殊要求(只要符合图的定义)，主要利用其无环特性解决问题。
（2）时间复杂度：Dijkstra 算法(使用二叉堆实现优先队列时)时间复杂度为O((V+E)logV)，Bellman - ford 算法时间复杂度为O(VE)，DAG 的算法复杂度取决于具体基于其特性的算法（例如基于拓扑排序的最短路径算法复杂度为O(V+E)）。
（3）算法原理：Dijkstra 算法基于贪心策略，每次选择距离源节点最短距离估计值最小的节点扩展；Bellman - ford 算法通过多次松弛操作来逐渐逼近最短路径；DAG 则是利用拓扑排序来有序地处理节点以解决问题。