728x90
반응형
Dijkstra algorithm
다익스트라 알고리즘은 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘
위의 예제를 통해 알아보자
각 정점은 인접한 정점에 대한 정보만 가짐. 인접하지 않는 정점까지의 비용은 무한대로 초기화함
먼저 집합N'에 A를 넣으면 A의 정보로 다음과 같은 테이블을 만듬
| A | B | C | D | E | F | |
| A | 0 | 10 | 30 | 15 | 무한대 | 무한대 |
| 집합N' | A | |||||
다음비용이 가장 작은 B를 N'에 넣음
| A | B | C | D | E | F | |
| A | 0 | 10 | 30 | 15 | 30 | 무한대 |
| 집합N' | A,B | |||||
B의 정보로 인해서 A->E까지의 경로가 업데이트 됨
다음단계에서는 비용이 가장 작은 D를 집합에 넣음
| A | B | C | D | E | F | |
| A | 0 | 10 | 20 | 15 | 30 | 35 |
| 집합N' | A, B, D | |||||
D를 추가하면서 A->C의 경로보다 A->D->C의 경로가 더 짧은 것을 인지함
다음단계에서는 비용이 집합에 없는 노드중에서 비용이 가장 작은 정점인 C,E중에서 C를 먼저 넣음
| A | B | C | D | E | F | |
| A | 0 | 10 | 20 | 15 | 30 | 25 |
| 집합N' | A, B, D, C | |||||
A->D->F의 경로(35)보다 A->D->C->F의 경로(25)로 더 짧으므로 업데이트 해줌
E, F를 집합 추가해서 위의 과정을 반복해도 더 이상 경로업데이트가 일어나지않음 따라서 위의 테이블이 최소경로임
[파이썬 자료구조] Floyd-Warshall Algorithm
Floyd-Warshall Algorithm i -> j까지의 최소비용경로가 존재할 때, 정점k를 발견했다고 가정 k를 통해서 가는 경로와 통하지 않는 경로를 비교하여 비용이 작은 쪽을 선택하는 알고리즘 k를 통해서 가는�
ohaengsa.tistory.com
728x90
반응형
'자료구조' 카테고리의 다른 글
| [파이썬 자료구조] 힙정렬(heap sort) (2) | 2020.06.27 |
|---|---|
| [파이썬 자료구조] Binary Heap (1) | 2020.06.27 |
| [파이썬 자료구조] Floyd-Warshall Algorithm (0) | 2020.06.21 |
| [파이썬 자료구조} Prim-Jarnik (0) | 2020.06.20 |
| [파이썬 자료구조] Partition or Disjoint Set (0) | 2020.06.20 |