14_shortest_path.py

  1"""
  2다익스트라 알고리즘 (Dijkstra's Algorithm)
  3Dijkstra's Shortest Path Algorithm
  4
  5가중치가 있는 그래프에서 단일 출발점 최단 경로를 찾는 알고리즘입니다.
  6음의 가중치가 없는 그래프에서 사용합니다.
  7"""
  8
  9import heapq
 10from collections import defaultdict
 11from typing import List, Dict, Tuple, Optional
 12
 13
 14# =============================================================================
 15# 가중치 그래프 표현
 16# =============================================================================
 17def create_weighted_graph(edges: List[Tuple[int, int, int]], directed: bool = False) -> Dict[int, List[Tuple[int, int]]]:
 18    """
 19    간선 리스트 (u, v, weight)로부터 가중치 인접 리스트 생성
 20    graph[u] = [(v, weight), ...]
 21    """
 22    graph = defaultdict(list)
 23    for u, v, w in edges:
 24        graph[u].append((v, w))
 25        if not directed:
 26            graph[v].append((u, w))
 27    return graph
 28
 29
 30# =============================================================================
 31# 1. 다익스트라 기본 구현
 32# =============================================================================
 33def dijkstra(graph: Dict[int, List[Tuple[int, int]]], start: int, n: int) -> List[int]:
 34    """
 35    다익스트라 알고리즘 (우선순위 큐 사용)
 36    시간복잡도: O((V + E) log V)
 37
 38    Args:
 39        graph: 인접 리스트 (노드 -> [(이웃, 가중치), ...])
 40        start: 시작 노드
 41        n: 총 노드 수
 42
 43    Returns:
 44        각 노드까지의 최단 거리 배열 (도달 불가시 무한대)
 45    """
 46    INF = float('inf')
 47    dist = [INF] * n
 48    dist[start] = 0
 49
 50    # (거리, 노드) 튜플을 저장하는 최소 힙
 51    pq = [(0, start)]
 52
 53    while pq:
 54        d, u = heapq.heappop(pq)
 55
 56        # 이미 처리된 거리보다 크면 스킵
 57        if d > dist[u]:
 58            continue
 59
 60        # 인접 노드 확인
 61        for v, weight in graph[u]:
 62            new_dist = dist[u] + weight
 63            if new_dist < dist[v]:
 64                dist[v] = new_dist
 65                heapq.heappush(pq, (new_dist, v))
 66
 67    return dist
 68
 69
 70# =============================================================================
 71# 2. 다익스트라 + 경로 추적
 72# =============================================================================
 73def dijkstra_with_path(
 74    graph: Dict[int, List[Tuple[int, int]]],
 75    start: int,
 76    end: int,
 77    n: int
 78) -> Tuple[int, List[int]]:
 79    """
 80    최단 거리와 함께 실제 경로도 반환
 81    """
 82    INF = float('inf')
 83    dist = [INF] * n
 84    dist[start] = 0
 85    parent = [-1] * n
 86
 87    pq = [(0, start)]
 88
 89    while pq:
 90        d, u = heapq.heappop(pq)
 91
 92        if d > dist[u]:
 93            continue
 94
 95        if u == end:
 96            break
 97
 98        for v, weight in graph[u]:
 99            new_dist = dist[u] + weight
100            if new_dist < dist[v]:
101                dist[v] = new_dist
102                parent[v] = u
103                heapq.heappush(pq, (new_dist, v))
104
105    # 경로 복원
106    if dist[end] == INF:
107        return INF, []
108
109    path = []
110    node = end
111    while node != -1:
112        path.append(node)
113        node = parent[node]
114    path.reverse()
115
116    return dist[end], path
117
118
119# =============================================================================
120# 3. 모든 쌍 최단 경로 (플로이드-워셜)
121# =============================================================================
122def floyd_warshall(n: int, edges: List[Tuple[int, int, int]]) -> List[List[int]]:
123    """
124    플로이드-워셜 알고리즘
125    모든 정점 쌍 사이의 최단 거리 계산
126    시간복잡도: O(V³)
127    """
128    INF = float('inf')
129    dist = [[INF] * n for _ in range(n)]
130
131    # 자기 자신으로의 거리는 0
132    for i in range(n):
133        dist[i][i] = 0
134
135    # 간선 정보 반영
136    for u, v, w in edges:
137        dist[u][v] = w
138
139    # k를 경유하는 경로 고려
140    for k in range(n):
141        for i in range(n):
142            for j in range(n):
143                if dist[i][k] + dist[k][j] < dist[i][j]:
144                    dist[i][j] = dist[i][k] + dist[k][j]
145
146    return dist
147
148
149# =============================================================================
150# 4. 벨만-포드 알고리즘 (음의 가중치 허용)
151# =============================================================================
152def bellman_ford(n: int, edges: List[Tuple[int, int, int]], start: int) -> Tuple[List[int], bool]:
153    """
154    벨만-포드 알고리즘
155    음의 가중치를 허용하며, 음의 사이클 검출 가능
156    시간복잡도: O(VE)
157
158    Returns:
159        (최단 거리 배열, 음의 사이클 존재 여부)
160    """
161    INF = float('inf')
162    dist = [INF] * n
163    dist[start] = 0
164
165    # V-1번 반복
166    for _ in range(n - 1):
167        for u, v, w in edges:
168            if dist[u] != INF and dist[u] + w < dist[v]:
169                dist[v] = dist[u] + w
170
171    # 음의 사이클 검출 (한 번 더 반복해서 갱신되면 음의 사이클)
172    has_negative_cycle = False
173    for u, v, w in edges:
174        if dist[u] != INF and dist[u] + w < dist[v]:
175            has_negative_cycle = True
176            break
177
178    return dist, has_negative_cycle
179
180
181# =============================================================================
182# 5. 네트워크 지연 시간 문제
183# =============================================================================
184def network_delay_time(times: List[List[int]], n: int, k: int) -> int:
185    """
186    노드 k에서 모든 노드로 신호가 도달하는 최소 시간
187    times[i] = [source, target, time]
188    도달 불가능하면 -1 반환
189    """
190    graph = defaultdict(list)
191    for u, v, w in times:
192        graph[u].append((v, w))
193
194    dist = dijkstra(graph, k, n + 1)  # 노드 번호가 1부터 시작
195
196    # 1~n번 노드 중 최대 거리
197    max_time = max(dist[1:n + 1])
198
199    return max_time if max_time != float('inf') else -1
200
201
202# =============================================================================
203# 6. K번째 최단 경로
204# =============================================================================
205def kth_shortest_path(
206    graph: Dict[int, List[Tuple[int, int]]],
207    start: int,
208    end: int,
209    k: int,
210    n: int
211) -> int:
212    """
213    K번째로 짧은 경로의 길이 반환
214    찾을 수 없으면 -1 반환
215    """
216    INF = float('inf')
217    count = [0] * n  # 각 노드에 도착한 횟수
218    pq = [(0, start)]
219
220    while pq:
221        d, u = heapq.heappop(pq)
222        count[u] += 1
223
224        if u == end and count[u] == k:
225            return d
226
227        # k번 이상 방문한 노드는 더 이상 확장하지 않음
228        if count[u] > k:
229            continue
230
231        for v, weight in graph[u]:
232            heapq.heappush(pq, (d + weight, v))
233
234    return -1
235
236
237# =============================================================================
238# 테스트
239# =============================================================================
240def main():
241    print("=" * 60)
242    print("다익스트라 & 최단 경로 알고리즘")
243    print("=" * 60)
244
245    # 예제 그래프
246    #       1
247    #    0 ---> 1
248    #    |      |
249    #  4 |      | 2
250    #    v      v
251    #    2 ---> 3
252    #       3
253    edges = [
254        (0, 1, 1),
255        (0, 2, 4),
256        (1, 3, 2),
257        (2, 3, 3),
258        (1, 2, 2)
259    ]
260
261    print("\n[그래프 구조]")
262    print("    0 --1--> 1")
263    print("    |        |")
264    print("    4        2")
265    print("    v        v")
266    print("    2 --3--> 3")
267    print("    (1->2 가중치 2)")
268
269    # 1. 다익스트라 기본
270    print("\n[1] 다익스트라 기본")
271    graph = create_weighted_graph(edges, directed=True)
272    dist = dijkstra(graph, 0, 4)
273    print(f"    시작점: 0")
274    for i, d in enumerate(dist):
275        print(f"    노드 {i}까지 거리: {d}")
276
277    # 2. 다익스트라 + 경로
278    print("\n[2] 다익스트라 + 경로 추적")
279    distance, path = dijkstra_with_path(graph, 0, 3, 4)
280    print(f"    0 -> 3 최단 거리: {distance}")
281    print(f"    경로: {' -> '.join(map(str, path))}")
282
283    # 3. 플로이드-워셜
284    print("\n[3] 플로이드-워셜 (모든 쌍 최단 거리)")
285    all_dist = floyd_warshall(4, edges)
286    print("    거리 행렬:")
287    for i, row in enumerate(all_dist):
288        row_str = [str(d) if d != float('inf') else '∞' for d in row]
289        print(f"    {i}: {row_str}")
290
291    # 4. 벨만-포드
292    print("\n[4] 벨만-포드 (음의 가중치 허용)")
293    edges_negative = [(0, 1, 4), (0, 2, 5), (1, 2, -3), (2, 3, 4)]
294    dist, has_neg_cycle = bellman_ford(4, edges_negative, 0)
295    print(f"    간선: {edges_negative}")
296    print(f"    최단 거리: {dist}")
297    print(f"    음의 사이클: {has_neg_cycle}")
298
299    # 음의 사이클 예제
300    edges_neg_cycle = [(0, 1, 1), (1, 2, -1), (2, 0, -1)]
301    dist, has_neg_cycle = bellman_ford(3, edges_neg_cycle, 0)
302    print(f"\n    음의 사이클 그래프: {edges_neg_cycle}")
303    print(f"    음의 사이클 존재: {has_neg_cycle}")
304
305    # 5. 네트워크 지연 시간
306    print("\n[5] 네트워크 지연 시간")
307    times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
308    n, k = 4, 2
309    result = network_delay_time(times, n, k)
310    print(f"    times={times}, n={n}, k={k}")
311    print(f"    모든 노드 도달 시간: {result}")
312
313    # 6. K번째 최단 경로
314    print("\n[6] K번째 최단 경로")
315    edges_k = [(0, 1, 1), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 1)]
316    graph_k = create_weighted_graph(edges_k, directed=True)
317    for k in range(1, 4):
318        dist = kth_shortest_path(graph_k, 0, 3, k, 4)
319        print(f"    0->3 {k}번째 최단 경로: {dist}")
320
321    print("\n" + "=" * 60)
322    print("주요 알고리즘 비교")
323    print("=" * 60)
324    print("""
325    | 알고리즘       | 시간복잡도      | 음의 가중치 | 용도                |
326    |---------------|----------------|------------|---------------------|
327    | 다익스트라     | O((V+E)log V) | 불가        | 단일 출발점 최단거리 |
328    | 벨만-포드      | O(VE)         | 가능        | 음의 가중치/사이클   |
329    | 플로이드-워셜  | O(V³)         | 가능*       | 모든 쌍 최단거리     |
330
331    * 플로이드-워셜도 음의 사이클이 있으면 올바르지 않음
332    """)
333
334
335if __name__ == "__main__":
336    main()