최단 경로

간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘

• 한 지점 ~ 다른 특정 지점

  • 다익스트라 알고리즘
    • 음의 가중치 허용 x
  • 벨만-포드 알고리즘
    • 음의 가중치 허용

• 모든 지점 ~ 다른 모든 지점

  • 플로이드-워샬 알고리즘

• 보통 그래프를 이용해 표현

  • 각 지점은 그래프에서 '노드'로 표현
  • 지점 간 연결된 도로는 그래프에서 '간선'으로 표현

• 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로 볼 수 있음
  

다익스트라 Dijkstra Algorithm

💡 특정 노드에서 출발해 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘

• GPS 소프트웨어의 기본 알고리즘으로 채택되곤 함

• 음의 간선이 없을 때 정상적으로 동작

  • 음의 간선이란?
    • 0보다 작은 값을 가지는 간선

• 그리디 알고리즘으로 분류

  • 그리디 기법을 사용한 알고리즘으로 프림 알고리즘과 유사
  • 매 상황에서 가장 적은 비용의 노드를 선택
  • BFS를 이용

• 단순하고 실행 속도 빠름

과정 및 구현

과정

1. 출발 노드 설정
2. 최단 거리 테이블 생성 및 초기화
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 3,4 반복
   

구현

• 각 노드에 대한 현재까지의 최단거리 정보를 1차원 리스트에 저장

'''
5 8
0 1 2
0 2 4
1 2 1
1 3 7
2 4 3
3 4 2
3 5 1
4 5 5
'''
def dijkstra(s, V): # s 출발 , V 마지막 정점 번호
    U = [0]* (V+1) # U 최소 비용이 결정된 정점 집합 
    U[s] = 1 # U = {s}
    for i in range(V + 1): # s에서 정점 i로 가는 비용 
        D[i] = adjM[s][i]

    # while U!= V: 남은 정점의 비용 결정 
    N = V + 1
    for _ in range(N-1) : # N-1개 정점의 비용 결정
        # D[w]가 최소인 w 결정 
        minV = INF
        w = 0
        for i in range(V+1):
            if U[i] == 0 and minV > D[i]: # 남은 정점 i 중 최소인 
                w = i 
                minV = D[i]
        U[w] = 1 # 최소인 w는 최소비용 D[w] 확정 
        # w에 인접인 정점에 대해 , 기존 비용 vs w를 거쳐가는 비용 비교 
        for v in range(V+1):
            if 0<adjM[w][v]<INF: # w에 인접인 v의 조건 
                D[v] = min(D[v], D[w] + adjM[w][v])

INF = 10000 # 문제에 따라 
V, E = map(int,input().split()) # 0~V번 정점, E간선 수 
adjM = [[INF]*(V+1) for _ in range(V+1)]
for i in range(V+1):
    adjM[i][i] = 0
for _ in range(E):
    u,v,w = map(int,input().split()) # u -> v, w : 가중치 
    adjM[u][v] = w

D = [0] * (V+1)
dijkstra(0,V)
print(D)

추천문제

SWEA 인수의 생일 파티