Djikstra.cs 3.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. // Adapted from JavaScript example in The Imposter's Hanbook by Rob Conery
  6. // Doesn't support negative edges!
  7. namespace Djikstra
  8. {
  9. class Path
  10. {
  11. public string Name;
  12. public int Cost;
  13. public bool Visited;
  14. public Path(string name, int cost, bool visited)
  15. {
  16. Name = name;
  17. Cost = cost;
  18. Visited = visited;
  19. }
  20. }
  21. class MemoTable
  22. {
  23. private List<Path> Table;
  24. public Path S;
  25. public MemoTable(string[] vertices)
  26. {
  27. S = new Path("S", 0, false);
  28. Table = new List<Path>() {S};
  29. foreach (var vertex in vertices)
  30. {
  31. Table.Add(new Path(vertex, int.MaxValue, false));
  32. }
  33. }
  34. private List<Path> GetCandidateVertices()
  35. {
  36. return Table.Where(x => !x.Visited).ToList();
  37. }
  38. public Path NextVertex()
  39. {
  40. List<Path> candidates = GetCandidateVertices();
  41. if (candidates.Any())
  42. {
  43. return candidates.OrderBy(x => x.Cost).First();
  44. }
  45. return null;
  46. }
  47. private Path GetEntry(string vertex) => Table.First(x => x.Name == vertex);
  48. private void SetCurrentCost(string vertex, int cost)
  49. {
  50. GetEntry(vertex).Cost = cost;
  51. }
  52. private void SetAsVisited(string vertex)
  53. {
  54. GetEntry(vertex).Visited = true;
  55. }
  56. private int GetCost(string vertex)
  57. {
  58. return GetEntry(vertex).Cost;
  59. }
  60. public void Evaluate(List<GraphItem> graph, Path vertex)
  61. {
  62. GraphItem[] edges = graph.Where(x => x.From == vertex.Name).ToArray();
  63. foreach (var edge in edges)
  64. {
  65. int currentVertexCost = GetCost(edge.From);
  66. int toVertexCost = GetCost(edge.To);
  67. int tentativeCost = currentVertexCost == int.MaxValue ? int.MaxValue : currentVertexCost + edge.Cost;
  68. if (tentativeCost < toVertexCost)
  69. SetCurrentCost(edge.To, tentativeCost);
  70. }
  71. SetAsVisited(vertex.Name);
  72. Path next = NextVertex();
  73. if (next != null)
  74. Evaluate(graph, next);
  75. }
  76. public override string ToString()
  77. {
  78. StringBuilder buffer = new StringBuilder();
  79. foreach (var element in Table)
  80. {
  81. buffer.AppendLine($"name: {element.Name}, cost: {element.Cost}, visited: {element.Visited}");
  82. }
  83. return buffer.ToString();
  84. }
  85. }
  86. class GraphItem
  87. {
  88. public string From;
  89. public string To;
  90. public int Cost;
  91. public GraphItem(string from, string to, int cost)
  92. {
  93. From = from;
  94. To = to;
  95. Cost = cost;
  96. }
  97. }
  98. class Program
  99. {
  100. static string[] vertices = { "A", "B", "C", "D", "E" };
  101. static List<GraphItem> graph = new List<GraphItem>()
  102. {
  103. new GraphItem("S", "A", 4),
  104. new GraphItem("S", "E", 2),
  105. new GraphItem("A", "D", 3),
  106. new GraphItem("A", "C", 6),
  107. new GraphItem("A", "B", 5),
  108. new GraphItem("B", "A", 3),
  109. new GraphItem("C", "B", 1),
  110. new GraphItem("D", "C", 3),
  111. new GraphItem("D", "A", 1),
  112. new GraphItem("E", "D", 1)
  113. };
  114. static void Main()
  115. {
  116. MemoTable memo = new MemoTable(vertices);
  117. memo.Evaluate(graph, memo.S);
  118. Console.WriteLine(memo.ToString());
  119. }
  120. }
  121. }