최단경로 알고리즘 풀이법 이론

 

다익스트라 알고리즘

한 출발노드에서 다른 노드들 까지의 최단거리를 구하는 알고리즘

 

1. 출발노드 설정

2. 최단거리 테이블 초기화 (자기 자신은 0, 다른 지점까지는 max)

3. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.

 

5. 3,4번을 반복한다.

 

 

구현 코드

import sys
input = sys.stdin.readline()
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
distance = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index


def dijkstra(start):
    distance[start] = 0
    visited[start] = True

    for j in graph[start]:
        distance[j[0]] = j[1] # j[0]번 노드로 가는 비용은 j[1]

    for i in range(n-1):
        now = get_smallest_node()
        visited[now] = True
        for j in graph[now]:
            cost = distance[now] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost


dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

시간복잡도 : O(v^2)

전체 노드의 개수가 5000개 이하일 때만 성공가능하다.

 

 

노드의 개수가 10000개가 넘을때 최단거리를 구하려면 우선순위큐를 사용한다.

최단거리가 가장 짧은 노드를 찾는 함수대신에 heapq을 사용하면 된다.

 

구현코드

import sys
import heapq
input = sys.stdin.readline()
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))



def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        
        //방문여부 확인 + 최단거리 갱신해야될지 검사
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

시간복잡도 : O(E log E) -> O(E log V^2) -> O(2E long V) -> O(ElogV)

 

 

 

플로이드 워셜 알고리즘

모든 노드에서 모든 노드까지의 최단경로를 구하는 알고리즘

(노드와 간선의 개수가 적을 때 사용한다.)

 

점화식 : dp[a][b] = min(dp[a][b], dp[a][k] + dp[k][b])

 

1. 2차원 테이블에 각 노드에서 다른 노드로 갈 때의 거리를 적는다. (자기자신은 0, 간선이 없으면 무한대)

2. 점화식에 따라 1번노드를 거쳐갈때, 2번노드를 거쳐갈때 ... 마지막 노드(마지막 노드는 생략해도됨)를 거쳐갈때의 dp를 구한다.

코드 구현 순서

1. graph는 2차원 리스트로 만든다. (INF로 초기화)

2. 자기자신 -> 자기자신 비용 0으로 초기화

3. 각 간선에 대한 정보 입력받아서 2차원리스트(graph)에 데이터넣기

4. 3중 for문으로 min(dp[a][b], dp[a][k] + dp[k][b]) 점화식 코드로 작성

 

 

구현코드

INF = int(1e9)

n = int(input())
m = int(input())

graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print("INFINITY", end=' ')
        else:
            print(graph[a][b], end=' ')
    print()

시간복잡도 : O(N^3)