[자료구조] 최단 경로

플로이드 와샬 알고리즘 

0) 정의 

-> 노드와 경로가 있을 때, 모든 노드를 최단 거리 (최소 비용)으로 연결하는 알고리즘

 

1) 작동 원리

-> 플로이드 와샬 알고리즘의 경우는 어떤 노드에서 시작해도 상관 x (모든 노드를 연결하는 것이 목적) 

 

· 가장 먼저 비용 배열과 방문 배열을 선언한다. 

· 0번 노드에서 시작 

· 0번 노드에서 갈 수 있는 노드들: 1, 4, 5번 노드들  -> 비용 배열 갱신 

· 방문하지 않은 노드들 중에서 최소값을 갖는 노드 (4번 노드)를 선택하여 시작 노드와 연결 

· 새로 추가된 4번 노드에서 탐색 작업 실시 

· 기존 값들과 비교하여 새로 연결될 경우의 필요 비용 계산, 최소값을 갖는 값으로 갱신 

· 방문하지 않는 노드들 중 최소 비용을 갖는 1번 노드 방문, 4번 노드 탐색 종료 

... 이와 같은 작업을 방문 배열에 방문하지 않은 노드가 없을 때 까지 반복 

2) 코드

values = [2**31-1 for i in range(n)]   # 비용 배열 선언
visited = [False for i in range(n)]   # 방문 배열 선언 

start = 0
visited[start] = True
values[start] = 0

while False is visited:   # 방문하지 않은 노드가 있다면 
    for i in costs:   # 노드 완전 탐색으로 비용배열의 거리 값 최소화 
        if(visited[i[1]] == False and i[0] == start):
            values[i[1]] = min(values[i[1]], i[2])
        if(visited[i[0]] == False and i[1] == start):
            values[i[0]] = min(values[i[0]], i[2])
            
   refer = 2**31 - 1
   for i in range(n):   # 방문하지 않은 노드 중 최소 비용 노드 위치 탐색 
       if(visited[i] == False and values[i] != 0): 
           refer - min(refer.values[i])
   answer = answer + refer 
   
   for i in range(n):   # 해당 노드 방문 여부 체크 
       if(visited[i] == False and values[i] == refer):
           visited[i] = True
           start = i 
           break

   

다익스트라 알고리즘

0) 정의 

-> 특정 노드에서 특정 노드까지 경로를 찾는 알고리즘 

 

1) 작동 원리 

· 가장 먼저 비용 배열과 방문 배열을 선언한다. 

* 다익스트라 알고리즘은 특정 노드에서 특정 노드까지의 최단 경로를 찾는 알고리즘이기 떄문에, 출발점이 필요 

 

· 0번 노드를 출발점으로 지정 

· 0번 노드에서 연결 가능한 노드 (1, 4, 5번 노드)의 비용 배열 갱신 

· 방문하지 않은 노드 중 최소 비용을 갖는 노드 (4번 노드) 방문 

· 4번 노드에서 방문할 수 있는 노드 확인 

* 플로이드 워셜 알고리즘과는 달리, 다익스트라 알고리즘에서는 현재 노드에서 비용 값을 같이 추가로 더해주어야 함 

 

· 비용 갱신

... 이와 같은 작업을 방문 배열에 방문하지 않은 노드가 없을 때 까지 반복 

2) 코드

visited = [False for _ in range(n)]   # 거리 배열 선언 
cost = [sys.maxsize for for _ in range(n)]   # 비용 배열 선언 
visited[0] = True   # 0번 노드를 시작점으로 설정  
cost[0] = 0 
length = len(visited)

while False in visited:   # 방문하지 않은 노드가 있다면 
    checkLoc = -1   # 방문하지 않은 노드 지역 중 최솟값 찾기 
    checkValue = sys.maxsize
    for i in range(length):
        if visited[i] == False and cost[i] < checkValue: 
            checkLoc = i 
            checkValue = cost[i] 
    if checkLoc == -1:    # 방문하지 않은 노드가 없다면 탈출 
        break
    visited[checkLoc] = True   
    for v1, v2, c in costs:   # 경로 완전탐색으로 비용배열 수정 
        if v1 == checkLoc and visited[v2] == False:
            cost[v2] = min(cost[v2], cost[v1] + c)
        if v2 == checkLoc and visited[v2] == False:
            cost[v1] = min(cost[v1], cost[v2] + c)