Johnson의 알고리즘

1 개요

Johnson's algorithm

Johnson의 알고리즘, 존손의 알고리즘

• 최단경로 알고리즘의 하나
• 전체 쌍 경로
• 밀집 그래프, 가중 그래프, 유향 그래프에 적용가능
• 최악사례 성능: [math]\displaystyle{ O (|V|^2 \log |V| + |V||E|) }[/math]

2 예시

3 같이 보기

• 최단경로 알고리즘

4 참고

• https://en.wikipedia.org/wiki/Johnson's_algorithm