Algorithm - 다익스트라, 플로이드 와샬

• 다익스트라
• 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구한다
• 가장 비용이 적은 노드를 하나씩 꺼낸 다음 그 노드를 거쳐가는 비용 계산

• 플로이드 와샬
• 모든 정점에서 다른 모든 정점으로의 최단 경로를 구한다
• 거쳐가는 정점을 하나씩 다 설정하여 직접 확인

다익스트라는 특정 출발점을 정하고 다른 정점까지의 최단거리를 구한다. 플로이드 와샬은 전체 그래프 상의 임의의 두 정점의 최단 거리를 모두 구한다. → 출발이 1 이라면 다익스트라는 2→3, 3→5 의 최단거리는 알 수 없지만 플로이드 와샬은 구할 수 있다. 하지만 플로이드 와샬의 시간이 그만큼 많이 걸린다(N^3).

다익스트라 (O((V + E)logV))

1. 하나의 정점에서 다른 정점으로 바로 갈 수 있으면 그 비용을, 갈 수 없다면 INF로 배열에 값을 저장한다.
→ 시작점 초기화(dp[0]=0)를 해주어야 함

2. 출발 노드로부터 시작하여 각 단계마다 가장 짧은 경로로 이어진 노드를 선택하여, 최단 거리를 갱신하고 출발 노드를 다음 가장 짧은 경로로 바꿔준다. → heap 사용

3. 그래프의 모든 노드를 방문할 때까지 위 단계를 반복합니다.

import heapq

def dijkstra(graph, start):
    # 시작점에서 각 노드까지의 거리를 무한대로 초기화
    distances = {node: float('inf') for node in graph}
    # 시작점에서 시작점까지의 거리는 0으로 설정
    distances[start] = 0
    
    # 우선순위 큐를 사용하여 방문할 노드를 저장
    queue = [(0, start)] # (거리, 노드) 튜플을 저장
    
    while queue:
        # 우선순위 큐에서 가장 짧은 거리의 노드 선택
        current_distance, current_node = heapq.heappop(queue)
        
        # 이미 처리한 노드인 경우 pass
        if current_distance > distances[current_node]:
              # if current_distance >= distances[current_node]: 로 하면 안됨!!
            continue
        
        # 현재 노드와 연결된 인접 노드들을 확인
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            # 더 짧은 경로를 찾은 경우 업데이트
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                # 우선순위 큐에 (거리, 노드) 튜플 추가
                heapq.heappush(queue, (distance, neighbor))
    
    return distances

# 예시 그래프
graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 3, 'B': 2, 'D': 4, 'E': 2},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 2, 'D': 3, 'F': 7},
    'F': {'D': 6, 'E': 7}
}

start_node = 'A'
print("출발 노드:", start_node)
print("최단 경로:", dijkstra(graph, start_node))

플로이드 와샬 (O(N^3))

• i(시작) → k(경유) → j(목적)로 이동한다 했을 때(k가 여러개여도 ok), 모든 점에 대하여 일일이 경유를 찍어보면, 반드시 한 번은 걸린다.

1. 하나의 정점에서 다른 정점으로 바로 갈 수 있으면 최소 비용을, 갈 수 없다면 INF로 2차원 배열에 값을 저장한다
주의) dist[i][i]의 경우 0으로 해둔다

2. 3중 for문을 통해 거쳐가는 정점을 설정한 후 해당 정점을 거쳐가서 비용이 줄어드는 경우에는 값을 바꿔준다.

3. 위의 과정을 반복해 모든 정점 사이의 최단 경로를 탐색한다.

import sys

INF = 10e9

def Floyd_Warshall():
		# 1 - 바로 연결한 간선들의 길이만 넣어주고, 나머진 INFINITE
    dist = [[INF]*n for i in range(n)] # 최단 경로를 담는 2차원 배열
    for i in range(n): # 최단 경로를 담는 배열 초기화
        for j in range(n):
            dist[i][j] = a[i][j]

		# 2,3 - 3중 포문으로 모든 경우에 대해서 비용이 줄어드는 경우 값을 바꿔준다.
    for k in range(n): # 거치는 점
        for i in range(n): # 시작점
            for j in range(n): # 끝점
                # k를 거쳤을 때의 경로가 더 적은 경로
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

n = 4 # 정점 수
a = [[0, 2, INF, 4],[2, 0, INF, 5],[3, INF, 0, INF],[INF, 2, 1, 0]]

dist = Floyd_Warshall()

for i in range(n):
    for j in range(n):
        print(dist[i][j],end=' ')
    print()