최단 경로 문제

1 개요

shortest path problem

最短 經路 問題

최단 경로 문제

• 두 꼭짓점 사이의 가장 짧은 경로를 찾는 문제
• 그래프에서 어떤 두 점 사이의 경로 중 가장 짧은 것을 구하는 문제
• (가중 그래프) 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제

 

2 종류

• ★ 단일-쌍 최단경로문제 : 어떤 지점에서 다른 어떤 지점으로 가능 최단경로 찾기
• 단일-출발 최단경로문제: 어떤 지점에서 출발하여 모든 지점에 도착하는 최단경로들 찾기
• 단일-도착 최단경로문제: 모든 지점에서 출발하여 어떤 지점에 도착하는 최단경로들 찾기
• 전체-쌍 최단경로문제: 모든 지점 쌍들 사이의 최단경로 찾기

3 같이 보기

• 문제
• 경로찾기
• 최단 경로
• 최단 경로 알고리즘

4 참고

• https://en.wikipedia.org/wiki/Shortest_path_problem
• http://terms.naver.com/entry.nhn?docId=854810&cid=50376&categoryId=50376