[TIL][Wed] 최단거리 알고리즘_다익스트라/플로이드 워셜

	Dijkstra 다익스트라	Floyd-Warshall 플로이드 워셜
어떤 문제에 사용할까?	한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우	모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 노드/간선 갯수 적을 떄 사용
사용처	가중 그래프(weighted graph)에서 하나의 정점으로부터 시작하여 각각의 노드로 가는 각각의 최단경로를 찾는 데 효율적.	가중 그래프에서 정점간 모든 쌍 사이에서 가장 짧은 경로를 찾는데 적합함. (all-pairs shortest path algorithm)
source - usecase	a single-source shortest path algorithm	a multi-source shortest path algorithm
정점 방문 방식	방문하지 않은 v중 최단거리가 가장 짧은 v를 선택(k)하고 한 단계씩 최단 거리를 구한다. 즉, 각 단계마다 특정 노드 k를 거쳐 가는 경우를 확인	각 단계마다 특정 노드 k를 거쳐 가는 경우를 확인한다. 단, a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사함 → 2차원리스트+3중반복
구현난이도	어려운 편	쉬운 편
시간복잡도	O(V2) O(ElogV) [최소힙] O(E + V*log(V)) [우선순위 큐/ 최소힙]	O(V^3) / O(N^3)
공간복잡도	O(V)	O(V^2) (2차원배열) / O(N^2)
음의 가중치 취급	X	O (+ / - 모두 지원)
접근법	greedy approach	Dynamic programming,
자료구조	우선순위 큐/ 최소힙	2차원 배열

다익스트라 알고리즘

How Dijkstra's Algorithm Works

• 각 노드에 대해 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며, 매번 현재 처리중인 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 계속 갱신한다. (최단 거리 테이블)

1. 출발 노드 설정
2. 최단 거리 테이블 설정 및 초기화
3. 방문하지 않은 노드 중 현재 최단 거리가 가장 짧은 노드를 확인하고
4. 해당 노드를 거쳐 다른 노드를 가는 비용을 계산하고
5. 최단 거리 테이블을 갱신한다.

스텍	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은 데이터

import heapq
import sys

'''
6 11
1
1 2 2 
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3 
4 5 1
5 3 1
5 6 2

'''
INF=sys.maxsize
#get data
V, E = list(map(int, sys.stdin.readline().strip().split()))
start=int(input())
#edges infoms

graph=[[] for _ in range(V+1)]
#최단 거리 테이블 초기화
distance=[INF]*(V+1)

#간선 정보를 입력받아서 그래프에 저장하기
for _ in range(E):
    #start, end, cost
    s, e, cost=list(map(int, sys.stdin.readline().strip().split()))
    graph[s].append((cost, e))
    

def dij(start):
    queue=[]
    #시작 노드 세팅
    heapq.heappush(queue, (0, start)) #큐에 넣어두기 
    distance[start]=0 #시작 노드니까 거리가 0

    while queue:
        #현재 큐에 들어있는 
        #최단 거리s가 가장 짧은 노드에 대해 정보를 꺼낸다. 
        dist, now=heapq.heappop(queue) 
        #지금 그곳으로 갈 거니까 
        # 거기까지 걸리는 거리 
        # now
        if distance[now]<dist:
            continue 
        #테이블에 있는 최단거리가 
        # 이 거리보다 더 짧으면 이미 찾은 것이다.
        # (이 노드가 이미 처리된 적이 있는 노드이다.)
        # 넘겨!
        
        #현재 노드와 연결된 다른 인접한 노드들을 확인핟나.
        #그 정보는 그래프 데이터의 현재 노드 안에 담겨 있다.
        # 거리, 목적지 순
        # cost는 dist(이 노드까지 오는 값)에 
        # 이 노드에서 저 노드까지 가는 거리값(data[0])를 더한다.
        
        for data in graph[now]:
            
            cost=dist+data[0]
            
            if cost<distance[data[1]]:
                #만약 이 cost가 
                # 지금 최단거리 테이블에 있는 
                # 저 노드까지 가는 값보다 작으면 갱신해준다. 
                distance[data[1]]=cost
                #이건 왜 하는 거지 
                heapq.heappush(queue, (cost, data[1]))
dij(start)

#모든 노드로 가기 위한 최단 거리를 출려 

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

#data=[list(map(int, sys.stdin.readline().strip().split())) for _ in range(E)]
#graph=[[]*(V+1)]

 

플로이드 워셜 알고리즘

Dab=min(Dab, Dak+Dkb)

직통과 경유를 비교하여 더 작은 값으로 갱신한다.

노드의 개수가 N개일 때 알고리즘상 N번의 단계를 수행한다. 이어서 각 단계마다 O(N2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다. → 따라서 이 방법을 써야할 때, 문제에서 노드의 갯수가 500개 이상을 주지 않음

1. 초기 상태에는 초기화를 하고 각 노드별 인접한 노드로의 cost만 체크하여 최단 거리 테이블을 만든다.
2. 1번 노드를 거쳐가는 경우를 고려해서 테이블을 갱신. 이중 반복문을 이용하여 모든 경우를 확인한다.
   • 즉, 모든 a,b에 대하여 a→1→b, 의 경우와 a→b의 경우를 비교하여 a→1→b가 더 작다면 작은 값으로 갱신한. 그렇게 된다면 모든 a→a, b→b, c→c ..등 자기자신으로 향하는 경우는 무조건 1번 노드를 거쳐갈 수 없고, 애초에 1번 노드에서 출발하는 값들과 1번 노드가 도착지인 경우는 따로 비교할 필요가 없다.

import sys 

#비교용 무한 설정용 
#INF=int(1e9) #10억
INF=sys.maxsize

#입력 받을 데이터 형식
'''
4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2

'''
#vertex와 edge의 갯수를 입력 받음
v=int(input())
e=int(input())

#2차원 리스트를 만들고 모든 값을 무한으로 초기화
graph=[[INF]*(v+1) for _ in range(v+1)]

#간선을 입력받아 임시로 저장하는 변수
temp_data=[list(map(int, sys.stdin.readline().strip().split())) for _ in range(e)]

#입력받은 간선 정보 중 cost를 그래프에 넣어준다.
#동시에 자기 자신에게 가는 항목은 모두 0으로 초기화    
for d in temp_data:
    s, e, cost=d
    graph[s][e]=cost
    graph[s][s]=0
    graph[e][e]=0

#이 시점 그래프
    
'''
- = INF
[
    [, -, -, -, -], 
    [-, 0, 4, -, 6], 
    [-, 3, 0, 7, -], 
    [-, 5, -, 0, 4], 
    [-, -, -, 2, 0],
    ]

'''

# 플로이드 워셜 알고리즘 
# 3중 반복을 돌며 직통구간과 경유구간을 비교해 
# 최소값을 넣어준다.

for k in range(v+1):
    for i in range(v+1):
        for j in range(v+1):
            graph[i][j]=min(graph[i][j], graph[i][k]+graph[k][j])

# 그래프 인쇄(1부터 시작!)
for i in range(1, v+1):
    for j in range(1, v+1):
        if graph[i][j]==INF:
            print("INF", end=' ')
        else:
            print(graph[i][j], end=' ')
    print()