BellmanFord.cs 2.1 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. // Adapted from JavaScript example in The Imposter's Handbook by Rob Conery
  5. namespace BellmanFord
  6. {
  7. class Path
  8. {
  9. public string From;
  10. public string To;
  11. public int Cost;
  12. public Path(string from, string to, int cost)
  13. {
  14. From = from;
  15. To = to;
  16. Cost = cost;
  17. }
  18. }
  19. class Program
  20. {
  21. static string[] vertices = { "S", "A", "B", "C", "D", "E" };
  22. static List<Path> graph = new List<Path>()
  23. {
  24. new Path("S", "A", 4),
  25. new Path("S", "E", -5),
  26. new Path("A", "C", 6),
  27. new Path("B", "A", 3),
  28. new Path("C", "B", -2),
  29. new Path("D", "C", 3),
  30. new Path("D", "A", 10),
  31. new Path("E", "D", 8)
  32. };
  33. static Dictionary<string, int> memo = new Dictionary<string, int>()
  34. {
  35. { "S", 0 },
  36. { "A", int.MaxValue },
  37. { "B", int.MaxValue },
  38. { "C", int.MaxValue },
  39. { "D", int.MaxValue },
  40. { "E", int.MaxValue }
  41. };
  42. static bool Iterate()
  43. {
  44. bool doItAgain = false;
  45. foreach (var fromVertex in vertices)
  46. {
  47. Path[] edges = graph.Where(x => x.From == fromVertex).ToArray();
  48. foreach (var edge in edges)
  49. {
  50. int potentialCost = memo[edge.From] == int.MaxValue ? int.MaxValue : memo[edge.From] + edge.Cost;
  51. if (potentialCost < memo[edge.To])
  52. {
  53. memo[edge.To] = potentialCost;
  54. doItAgain = true;
  55. }
  56. }
  57. }
  58. return doItAgain;
  59. }
  60. static void Main()
  61. {
  62. for (int i = 0; i < vertices.Length; i++)
  63. {
  64. if (!Iterate())
  65. break;
  66. }
  67. foreach (var keyValue in memo)
  68. {
  69. Console.WriteLine($"{keyValue.Key}: {keyValue.Value}");
  70. }
  71. }
  72. }
  73. }