이산수학 최단 경로 알고리즘

이산수학 그래프5: 최단경로 알고리즘(1)

• One → One : MST알고리즘
• One → all : 다익스트라, 벨만포드
• all → all : 플루이드워샬

다익스트라 알고리즘 (Dijkstra)

• 한 정점에서 다른 모든 정점으로의 최단경로를 찾는 알고리즘
• 방향그래프, 비방향그래프 모두 적용 가능
• 가중치값이 음수가 아니어야함
• 방법
  • (출발 정점의 가중치를 0, 갈수 없는 곳의 가중치를 무한대로 둠)
  1. 출발 정점을 우선순위 큐에 넣음
  2. 큐에서 정점 하나를 꺼내 해당 정점에서 갈 수 있는 정점들을 확인하고 가중치를 업데이트하여 우선순위 큐에 넣음
     (큐에서 꺼낸 정점이 이미 도달한 정점의 경우 넘김)
  3. 큐가 빌때까지 2번 반복

벨만포드 알고리즘 (Bellman-Ford)

• 한 정점에서 다른 모든 정점으로의 최단경로를 찾는 알고리즘
• 방향그래프, 비방향그래프 모두 적용 가능
• 가중치값이 음수일 때도 적용 가능
• 사이클이 존재하면 안됨
• 방법
  1. 출발점을 가중치 0, 나머지를 가중치 무한대로 둠 (D[1]=0, D[i]= 무한대 for all i ∈ {2,3,..,n})
  2. for all i ∈ {2,3,...n}
     D[i] = min (D[k] + d(ki)) for i 와 직접 연결선이 있는 k
  3. 2번을 D[i]의 변화가 더 이상 발생하지 않을때까지 반복한다