一、DAG

全称为“Directed Acyclic Graph”，中文意思为：有向无环图，它由有限个顶点和“有向边”组成，从任意顶点出发，经过若干条有向边，都无法回到该顶点，这种图就是有向无环图。

1.DAG原理主要包括以下几个方面：

1. 有向性：DAG的边是有方向的，这意味着每条边都有一个起点和终点，表示从一个节点到另一个节点的关系。
2. 无环性：DAG不包含任何循环路径，即从某个节点出发不能回到该节点。这一特性保证了图中没有重复的路径，确保了数据的顺序性和层次结构。
3. 拓扑排序：由于DAG的无环性质，可以进行拓扑排序。拓扑排序是一种线性排列，使得对于每一条有向边，由起点指向终点的顺序都被保持。这在任务调度、依赖关系处理等场景中非常有用。

2.以XDAG项目为例

在XDAG的网络中，其实是一个个动态的“局域网”的组合，所有的交易用户隶属于不同的“局域网”，不同的“局域网”联合起来构成整个XDAG的网络。“局域网”建立的基础是具有验证交易（挖矿）能力的节点（这个节点可以是单个矿工，也有可能是矿场或矿池），当用户发起交易时，会将交易发送到自己所在“局域网”的矿工，矿工会验证数字签名、资产余额、数据格式、数据完整性等信息，当遇到无效交易后，便会进行标记，然后矿工会打包确认好的信息并向全网发送，其他“局域网”的矿工收到后会验证自己收到的这个数据包是不是合法的，如果都没有问题，那么这些交易就会被承认。

在XDAG的网络，主节点组成主链，主链是所有节点难度加和最高的一条。和比特币网络一样，所有的交易都需要排序，那么也就是所有的节点是需要排序的，主节点的功能就是确定顺序，除此之外，主节点还负责记录挖矿收益，在XDAG中，每64s出一个块，出块同时奖励矿工1024个xdag，但是主节点不记录其他任何交易，因此可以将主节点看成是一个空块，而其他的节点才负责记录交易。主节点的产生需要挖矿，交易节点是系统自动生成。

3.DAG技术的特点：

1. 交易速度快

DAG实现的局部处理和并行结算，可以使得交易速度大幅度提升。

1. 拓展性强

因为各个节点，无需等待同步其他的节点数据，使得记账节点很容易答复延展，因此DAG很适用于物联网类项目。

1. 作恶难度更大

相比于链式结构，在DAG图式结构中恶意修改的难度会大很多，因为DAG拥有着很多的出度和入度，假如要修改某一个节点，那么对应的出入度都要进行修改。 

4.DAG优点：

（1）支持并发交易，所以吞吐量高。
（2）没有交易费用。

DAG缺点：

（1）天生不支持智能合约，限制了其应用场景。
（2）只有当形网络形成一定规模时，DAG才可以安全的被应用。现有的DAG的项目还是暂时采用的中心化的共识策略，因为网络规模不够。
（3）安全性有待验证。

5.应用场景：

1. 任务调度：在项目管理中，用于表示任务之间的依赖关系。例如，构建项目的甘特图或PERT图。
2. 版本控制系统：例如Git，使用DAG来表示代码提交的历史，确保每个提交都有一个唯一的前驱。
3. 数据处理管道：用于表示数据流动的顺序，如ETL（提取、转换、加载）过程。

二、Dijkstra算法

是解决单源有权图最短路径的一个算法，本质是贪心算法，它只适用于不含负权边的图。

1.要点

每次从 「未求出最短路径的点」中 取出 距离距离起点 最小路径的点，以这个点为桥梁 刷新「未求出最短路径的点」的距离。

2.案例：以 A 点为顶点，求到其他点的最短路径。

（重点）算法要点

result：已求出 最小路径的顶点

notFound：未求出 最小路径的顶点，里面的值是 到起点的距离

每次从 「未求出最短路径的点」中 取出 距离距离起点 最近的点，以这个点为桥梁 刷新「未求出最短路径的点」的距离。

初始，result={A(0)} 中只有起点 A，notFound={B(2),C(∞),D(6)} 中是除了 A 点的其他点，里面的值是到起点的距离（例如 B(2) 代表 B点到起点的距离为 2），然后，从「未求出最短路径的点」notFound 中取出 最短路径的点 B(2) 然后通过 B(2) 为桥梁 刷新「未求出最短路径的点」的距离。

1.取出最短路径的点：

从「未求出最短路径的点」notFound 中取出 最短路径的点 B(2)，放入结果 result 中，结果如下：

「未求出最短路径点」 notFound={C(∞),D(6)}，「已求出最短路径的点 」result={A(0),B(2)}

刷新距离：

通过 B(2) 为桥梁，刷新距离。

例如 AD = 6 < AB + BD = 4 以 B(2) 为桥梁的距离更短，就刷新「未求出最短路径点」D(6) 的距离为 D(4)

notFound={C(∞),D(4)}

同理刷新 C(∞) 的距离为 C(5) ，最后结果如下：

「未求出最短路径点」 notFound={C(5),D(4)} ，「已求出最短路径的点」`result={A(0),B(2)} `

然后，从「未求出最短路径的点」notFound 中取出 最短路径的点 D(4) ，然后通过 D(4) 为桥梁 刷新「未求出最短路径的点」的距离

同理，最后结果如下：

「未求出最短路径点」 notFound={C(5)} ，「已求出最短路径的点」result={A(0),B(2),D(4)}

然后，从「未求出最短路径的点」notFound 中取出 最短路径的点 C(5) ，算法结束

result={A(0),B(2),D(4),C(5)} 就是最终所求的 最短距离。

3.代码

这里使用 -1 表无穷大，下面是 Java 代码和测试案例

public class Dijkstra {
    public static int[] dijkstra(int[][] graph,int startVertex){
        //初始化 以求出最短路径的点 result[]        int length = graph.length;
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            result[i] = -1;
        }
        result[startVertex] = 0 ;
        // 初始化 未求出最短路径的点 notFound[]        int[] notFound = new int[length];
        for (int i = 0; i < length; i++) {
            notFound[i] = graph[startVertex][i];
        }
        notFound[startVertex] = -1;
        // 开始 Dijkstra 算法        for (int i = 1; i < length; i++) {
            //1. 从「未求出最短路径的点」notFound 中取出 最短路径的点            //1.1 找到最短距离的点            int min = Integer.MAX_VALUE;
            int minIndex = 0;
            for (int j = 0; j < length; j++) {
                if (notFound[j] > 0 && notFound[j] < min){
                    min = notFound[j];
                    minIndex = j;
                }
            }
            //1.2 将最短距离的点 取出 放入结果中            result[minIndex] = min;
            notFound[minIndex] = -1;
            //2. 刷新 「未求出最短距离的点」 notFound[] 中的距离            //2.1 遍历刚刚找到最短距离的点 (B) 的出度 (BA、BB、BC、BD)            for (int j = 0; j < length; j++) {
                // 出度可通行(例如 BD:graph[1][3]  > 0)                // 出度点不能已经在结果集 result中(例如 D: result[3] == -1)                if (graph[minIndex][j] > 0
                && result[j] == -1){
                    int newDistance = result[minIndex] + graph[minIndex][j];
                    //通过 B 为桥梁，刷新距离                    //（比如`AD = 6 < AB + BD = 4` 就刷新距离）（ -1 代表无限大）                    if (newDistance < notFound[j] || notFound[j]==-1){
                        notFound[j] = newDistance;
                    }
                }
            }

        }
        return result;
    }
    /** 测试案例 */
    public static void main(String[] args) {
        char[] vertices = new char[]{'A','B','C','D'};
        int[][] graph = new int[][]{
                {0, 2, -1, 6}
                , {2, 0, 3, 2}
                , {-1, 3, 0, 2}
                , {6, 2, 2, 0}};
        int[] dijkstra = dijkstra(graph, 0);
        for (int i : dijkstra) {
            System.out.println(i);
        }
    }}

测试结果

0
2
5
4

4.应用场景：

1. 网络路由：在计算机网络中，Dijkstra算法可以帮助确定数据包在网络中从源节点到目标节点的最佳路径。
2. 地图导航：在GPS导航系统中使用，计算从当前位置到目的地的最短行驶路线。
3. 机器人路径规划：在机器人技术中，用于规划机器人在环境中移动的最优路径。

三、Bellman-Ford算法

是一种处理存在负权边的单元最短路问题的算法。解决了Dijkstra无法求的存在负权边的问题。 虽然其算法效率不高，但是也有其特别的用处。其实现方式是通过m次迭代求出从源点到终点不超过m条边构成的最短路的路径。一般情况下要求途中不存在负环。但是在边数有限制的情况下允许存在负环。因此Bellman-Ford算法是可以用来判断负环的。

1.应用：Bellman-Ford算法

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。
注意：图中可能存在负权回路。
输入格式
第一行包含三个整数n，m，k。
接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。
如果不存在满足条件的路径，则输出“impossible”。
数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3

2.代码实现(Code)

int dist[N],backup[N];//dist距离，backup用来存上一次的结果。struct edge//用来存边{
    int a;
    int b;
    int w;}Edge[M];int Bellman_Ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;//初始化    for(int i = 0 ; i < k ; i++)//遍历k次    {
        memcpy(backup,dist,sizeof dist);//存上一次答案。        for(int j = 0 ; j < m ; j++)
        {
            int a = Edge[j].a, b = Edge[j].b, w = Edge[j].w;
            dist[b] = min(dist[b],backup[a] + w);
        }//遍历所有边    }
    if(dist[n] > 0x3f3f3f3f/2) return -1;
    /*这里不像Dijkstra写等于正无穷是因为可能有负权边甚至是负环的存在，    使得“正无穷”在迭代过程中受到一点影响。*/
    return dist[n];}

3.应用场景：

1. 金融领域：例如，计算存在负债的投资组合，表示不同投资间的关系。
2. 网络路由协议：在某些路由协议（如RIP）中，Bellman-Ford算法用于动态计算最短路径。
3. 负权边问题：解决涉及负权边的图的最短路径问题，比如某些时间延迟的计算。

四、DAG、Dijkstra算法和Bellman-Ford算法之间的异同点的对比表格：

特性	DAG（有向无环图）	Dijkstra算法	Bellman-Ford算法
类型	图的结构	最短路径算法	最短路径算法
特征	没有回路的有向图	计算非负权重边的最短路径	支持负权重边，检测负权回路
适用场景	任务调度、版本控制、数据流	网络路由、地图导航	金融分析、动态路由协议
时间复杂度	拓扑排序：O(V + E)	O((V + E) log V)（优先队列）	O(VE)
返回结果	图的结构	从源节点到其他节点的最短路径及距离	从源节点到其他节点的最短路径及距离，并检测负权回路
边权要求	不适用边权，结构性定义	只支持非负权重	支持负权重