狄克斯特拉 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; } }
相关推荐
湾区人工智能 2020-11-20
Pokemogo 2020-11-16
baijingjing 2020-11-16
baijingjing 2020-11-15
Site 2020-11-07
lwnylslwnyls 2020-11-06
justaipanda 2020-11-05
MachineIntellect 2020-11-02
xueyuediana 2020-10-30
GeraldJones 2020-10-30
Tips 2020-10-29
baijingjing 2020-10-28
baijingjing 2020-10-27
硕鼠 2020-10-26
playoffs 2020-10-26
scuyxi 2020-10-25
playoffs 2020-10-25
yise001 2020-10-23