狄克斯特拉 Dijkstra 算法 C#实现

今天在看《算法图解》，看了加权最小路径算法，决定用代码实现一下。

首先是画有向图，在网上找了一下，有不错的开源软件graphviz,该源代码托管在GitLab上。该软件是一个图形可视化软件。
画了一个有向图如下：

画图用的代码：

digraph dijkstra{
start->A[label="6"]
start->B[label="2"]
A->end[label="1"]
B->A[label="3"]
B->end[label="5"]
}

我建了一个控制台应用程序：

class Program
    {

        public static List<Node> NodeList { get; set; }
        public static Dictionary<string,int> CostDictionary { get; set; }
        public static Dictionary<string, string> ParentDictionary { get; set; }
        public static List<string> CheckedNodeName { get; set; }

        public Program()
        {
            NodeList= new List<Node>
            {
                new Node
                {
                    NodeName = "start",
                    RelatedNode = new Dictionary<string, int>()
                    {
                        {"A", 6},
                        {"B", 2}
                    }
                },
                new Node
                {
                    NodeName = "A",
                    RelatedNode = new Dictionary<string, int>()
                    {
                        {"end", 1}
                    }
                },
                new Node
                {
                    NodeName = "B",
                    RelatedNode = new Dictionary<string, int>()
                    {
                        {"A", 3},
                        {"end", 5}
                    }
                },
                new Node
                {
                    NodeName = "end",
                    RelatedNode = new Dictionary<string, int>()
                }
            };
            CostDictionary = new Dictionary<string,int>()
            {
                {"A",6},
                {"B",2},
                {"end",int.MaxValue}
            };

            ParentDictionary = new Dictionary<string, string>()
            {
                {"A","start"},
                {"B","start"},
                {"end",""}
            };

            CheckedNodeName=new List<string>();
           
        }

        static void Main(string[] args)
        {
            var progra=new Program();
            Console.WriteLine($"{"parent",10}|{"node",10}|{"cost",10}");
            foreach ( var item in NodeList.SelectMany(node=>node.RelatedNode,(node,relatenode)=>new {node.NodeName,relatenode}))
            {
                Console.WriteLine($"{item.NodeName,10}|{item.relatenode.Key,10}|{item.relatenode.Value,10}");
            }

            while (CheckedNodeName.Count!=CostDictionary.Count)
            {
                //找到Cost最小的节点
                var currentNode = FindMinCostNode(CostDictionary);
                //取出relatednode，
                if (currentNode != null)
                {
                    //循环如果subNode的Cost小于CostDictionary的Cost
                    foreach (var subNode in currentNode.RelatedNode)
                    {
                        if (subNode.Value < CostDictionary[subNode.Key])
                        {
                            //替换
                            CostDictionary[subNode.Key] = subNode.Value+ CostDictionary[currentNode.NodeName];
                            ParentDictionary[subNode.Key] = currentNode.NodeName;
                        }
                    }
                    CheckedNodeName.Add(currentNode.NodeName);
                }
            }

            Console.WriteLine("最短路径:"+ GetTheMinCostPath());

            Console.WriteLine("最短路径开销:"+CostDictionary["end"]);

            Console.ReadKey();
        }

        public static string GetTheMinCostPath()
        {
            bool isStart=false;
            string startKey="end";
            string path= "end=>";
            while (!isStart)
            {
               
                path += ParentDictionary[startKey]+"=>";
                startKey = ParentDictionary[startKey];
                if (!ParentDictionary.ContainsKey(ParentDictionary[startKey]))
                {
                    path += ParentDictionary[startKey];
                    isStart = true;
                }
            }

            return path;
        }

        public static Node FindMinCostNode(Dictionary<string,int> costDictionary)
        {
            var costItems= costDictionary.Where(c => !CheckedNodeName.Contains(c.Key)).ToList();
            if (costItems.Any())
            {
                var minCostItem = costItems.OrderBy(c => c.Value).First().Key;
                return NodeList.FirstOrDefault(n => n.NodeName == minCostItem);
            }
            return null;
        }
    }

    public class Node
    {
        public string NodeName { get; set; }
        public Dictionary<string, int> RelatedNode { get; set; }
    }

    public class CostItem
    {
        public string ParentName { get; set; }
        public string NodeName { get; set; }
        public int Cost { get; set; }
    }