■ 다익스트라(Dijkstra) 알고리즘을 사용해 그래프에서 최단 경로 리스트를 구하는 방법을 보여준다.
▶ Graph.cs
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
namespace TestProject; /// <summary> /// 그래프 /// </summary> public class Graph { //////////////////////////////////////////////////////////////////////////////////////////////////// Field ////////////////////////////////////////////////////////////////////////////////////////// Private #region Field /// <summary> /// 버텍스 딕셔너리 /// </summary> private Dictionary<string, Dictionary<string, int>> vertexDictionary = new Dictionary<string, Dictionary<string, int>>(); #endregion //////////////////////////////////////////////////////////////////////////////////////////////////// Method ////////////////////////////////////////////////////////////////////////////////////////// Public #region 에지 추가하기 - AddEdge(startNode, endNode, weight) /// <summary> /// 에지 추가하기 /// </summary> /// <param name="startNode">시작 노드</param> /// <param name="endNode">종료 노드</param> /// <param name="weight">가중치</param> public void AddEdge(string startNode, string endNode, int weight) { if(!this.vertexDictionary.ContainsKey(startNode)) { this.vertexDictionary[startNode] = new Dictionary<string, int>(); } this.vertexDictionary[startNode][endNode] = weight; } #endregion #region 최단 경로 리스트 구하기 - GetShortestPathList(startNode, endNode) /// <summary> /// 최단 경로 리스트 구하기 /// </summary> /// <param name="startNode">시작 노드</param> /// <param name="endNode">종료 노드</param> /// <returns>최단 경로 리스트</returns> public List<string> GetShortestPathList(string startNode, string endNode) { Dictionary<string, int> distanceDictionary = new Dictionary<string, int>(); Dictionary<string, string> previousNodeDictionary = new Dictionary<string, string>(); List<string> nodeList = new List<string>(); List<string> pathList = null; foreach(KeyValuePair<string, Dictionary<string, int>> keyValurPair in vertexDictionary) { if(keyValurPair.Key == startNode) { distanceDictionary[keyValurPair.Key] = 0; } else { distanceDictionary[keyValurPair.Key] = int.MaxValue; } nodeList.Add(keyValurPair.Key); } while(nodeList.Count != 0) { nodeList.Sort((x, y) => distanceDictionary[x].CompareTo(distanceDictionary[y])); string smallestNode = nodeList[0]; nodeList.Remove(smallestNode); if(smallestNode == endNode) { pathList = new List<string>(); while(previousNodeDictionary.ContainsKey(smallestNode)) { pathList.Add(smallestNode); smallestNode = previousNodeDictionary[smallestNode]; } pathList.Add(startNode); pathList.Reverse(); } if(distanceDictionary[smallestNode] == int.MaxValue) { break; } if(vertexDictionary.ContainsKey(smallestNode)) { foreach(KeyValuePair<string, int> neighbor in vertexDictionary[smallestNode]) { if (!distanceDictionary.ContainsKey(neighbor.Key)) { distanceDictionary[neighbor.Key] = int.MaxValue; nodeList.Add(neighbor.Key); } var alt = distanceDictionary[smallestNode] + neighbor.Value; if (alt < distanceDictionary[neighbor.Key]) { distanceDictionary[neighbor.Key] = alt; previousNodeDictionary[neighbor.Key] = smallestNode; } } } } return pathList; } #endregion } |
▶ Program.cs
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
namespace TestProject; /// <summary> /// 프로그램 /// </summary> class Program { //////////////////////////////////////////////////////////////////////////////////////////////////// Method ////////////////////////////////////////////////////////////////////////////////////////// Static //////////////////////////////////////////////////////////////////////////////// Private #region 프로그램 시작하기 - Main() /// <summary> /// 프로그램 시작하기 /// </summary> static void Main() { Graph graph = new Graph(); graph.AddEdge("A", "B", 4); graph.AddEdge("A", "C", 2); graph.AddEdge("A", "D", 7); graph.AddEdge("B", "D", 1); graph.AddEdge("B", "C", 3); graph.AddEdge("D", "E", 5); graph.AddEdge("E", "F", 2); List<string> shortestPathList = graph.GetShortestPathList("A", "F"); Console.WriteLine("A에서 F까지의 최단 경로 :"); Console.WriteLine(string.Join(" -> ", shortestPathList)); } #endregion } |
