c# 有向无环图最短路径

对于有向无环图的最短路径问题，可以使用拓扑排序和动态规划的方法来解决。以下是一个使用 C# 编写的示例代码：

using System;
using System.Collections.Generic;

public class Graph
{
    private int V; // 图中顶点的数量
    private List<List<Node>> adj; // 邻接表，用于存储图的边

    public Graph(int v)
    {
        V = v;
        adj = new List<List<Node>>();

        for (int i = 0; i < V; i++)
        {
            adj.Add(new List<Node>());
        }
    }

    public void AddEdge(int u, int v, int weight)
    {
        Node node = new Node(u, v, weight);
        adj[u].Add(node);
    }

    public void ShortestPath(int source)
    {
        int[] dist = new int[V];
        for (int i = 0; i < V; i++)
        {
            dist[i] = int.MaxValue;
        }

        dist[source] = 0;

        // 拓扑排序
        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[V];

        for (int i = 0; i < V; i++)
        {
            if (!visited[i])
            {
                TopologicalSortUtil(i, visited, stack);
            }
        }

        // 计算最短路径
        while (stack.Count > 0)
        {
            int u = stack.Pop();

            if (dist[u] != int.MaxValue)
            {
                foreach (var node in adj[u])
                {
                    if (dist[u] + node.Weight < dist[node.V])
                    {
                        dist[node.V] = dist[u] + node.Weight;
                    }
                }
            }
        }

        // 输出最短路径
        Console.WriteLine("顶点\t距离");
        for (int i = 0; i < V; i++)
        {
            Console.WriteLine(i + "\t" + dist[i]);
        }
    }

    private void TopologicalSortUtil(int v, bool[] visited, Stack<int> stack)
    {
        visited[v] = true;

        foreach (var node in adj[v])
        {
            if (!visited[node.V])
            {
                TopologicalSortUtil(node.V, visited, stack);
            }
        }

        stack.Push(v);
    }

    private class Node
    {
        public int U { get; set; } // 边的起始顶点
        public int V { get; set; } // 边的结束顶点
        public int Weight { get; set; } // 边的权重

        public Node(int u, int v, int weight)
        {
            U = u;
            V = v;
            Weight = weight;
        }
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        int V = 6; // 图中顶点的数量
        Graph graph = new Graph(V);

        graph.AddEdge(0, 1, 2);
        graph.AddEdge(0, 4, 1);
        graph.AddEdge(1, 2, 3);
        graph.AddEdge(4, 2, 2);
        graph.AddEdge(4, 5, 4);
        graph.AddEdge(2, 3, 6);
        graph.AddEdge(5, 3, 1);

        int source = 0;
        graph.ShortestPath(source);
    }
}

在这个示例代码中，我们首先创建了一个有向无环图对象，然后使用`AddEdge`方法添加图的边。然后，我们调用`ShortestPath`方法来计算从给定源顶点到其他顶点的最短路径。最后，我们输出了所有顶点的最短路径。

请注意，这里的示例代码使用了拓扑排序和动态规划的思想来解决有向无环图的最短路径问题。这种方法适用于没有负权边的图。如果图中存在负权边，则需要使用其他算法，如 Bellman-Ford 算法或 Dijkstra 算法的变种。