如何用C#实现求有向图的最长路径？

Z时代
2024-01-10
分类：IT

题目描述

公司最近的项目里有一个计算流程长度的需求，即要把整个流程中最长的流程找出来，其实质便是计算出有向图的最长路径。
如图所示：

计算出图中A-E最长的路径，即：A-B-C-D-E

回答：

    public class RouteEngine<T>
    {
        private List<Node<T>> Nodes { get; set; }
        private Dictionary<string, int> RouteList { get; set; } = new Dictionary<string, int>();
        public RouteEngine(List<Node<T>> nodes)
        {
            Nodes = nodes;
        }
        private void InterateRoute(Node<T> node, string route, int dis)
        {
            if (node.Prevs.Any())
            {
                foreach (var prev in node.Prevs)
                {
                    RouteList[prev.Key.Name + "," + route] = dis + prev.Value;
                    InterateRoute(prev.Key, prev.Key.Name + "," + route, dis + prev.Value);
                }
            }
        }
        public (List<Route<T>>, HashSet<Node<T>>) GetRoutes(Node<T> start, Node<T> end, bool shortest)
        {
            InterateRoute(end, end.Name, 0);
            var list = new List<Route<T>>();
            var nodes = new HashSet<Node<T>>();
            var routes = RouteList.Where(k => k.Key.StartsWith(start.Name) && k.Key.EndsWith(end.Name));
            var route = (shortest ? routes.OrderBy(x => x.Value) : routes.OrderByDescending(x => x.Value)).FirstOrDefault().Key;
            string[] strs = route.Split(',');
            for (var i = 0; i < strs.Length - 1; i++)
            {
                Node<T> src = Nodes.Find(n => n.Name.Equals(strs[i]));
                Node<T> dest = Nodes.Find(n => n.Name.Equals(strs[i + 1]));
                list.Add(new Route<T>(src, dest, dest.Prevs[src]));
                nodes.Add(src);
                nodes.Add(dest);
            }
            return (list, nodes);
        }
    }
    public class Route<T>
    {
        public Route(Node<T> src, Node<T> dest, int distance)
        {
            Source = src;
            Dest = dest;
            Distance = distance;
        }
        public Node<T> Source { get; set; }
        public Node<T> Dest { get; set; }
        public int Distance { get; set; }
    }
    public class Node<T>
    {
        public Node(string name)
        {
            Name = name;
            Prevs = new Dictionary<Node<T>, int>();
        }
        public string Name { get; set; }
        public Dictionary<Node<T>, int> Prevs { get; set; }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Node<string> a = new Node<string>("A");
            Node<string> b = new Node<string>("B");
            Node<string> c = new Node<string>("C");
            Node<string> d = new Node<string>("D");
            Node<string> e = new Node<string>("E");
            b.Prevs.Add(a, 1);
            c.Prevs.Add(b, 2);
            c.Prevs.Add(a, 2);
            d.Prevs.Add(b, 3);
            d.Prevs.Add(c, 0);
            e.Prevs.Add(b, 9);
            e.Prevs.Add(d, 4);
            List<Node<string>> nodes = new List<Node<string>>()
            {
                a,
                b,
                c,
                d,
                e
            };
            var engine = new RouteEngine<string>(nodes);
            var (routes, routeNodes) = engine.GetRoutes(a, e, false);
            foreach (var x in routes)
            {
                Console.WriteLine(x.Source.Name + "->" + x.Dest.Name + ":" + x.Distance);
            }
            Console.WriteLine("最长路径：" + string.Join("->", routeNodes.Select(x => x.Name)) + ":" + routes.Sum(r => r.Distance));
            (routes, routeNodes) = engine.GetRoutes(a, e, true);
            foreach (var x in routes)
            {
                Console.WriteLine(x.Source.Name + "->" + x.Dest.Name + ":" + x.Distance);
            }
            Console.WriteLine("最短路径：" + string.Join("->", routeNodes.Select(x => x.Name)) + ":" + routes.Sum(r => r.Distance));
        }
    }