최단 경로 탐색 계산기: Bellman–Ford 방법으로 유향 그래프의 최단 경로를 계산합니다. 출발점에서 도달 가능한 음수 순환이 있으면 계산을 거절합니다.
최단 경로 탐색 계산기 사용법
- 입력 항목은 유향 간선: 출발번호 도착번호 비용·노드 수·출발 노드·목표 노드입니다.
- 출발·도착 노드와 비용을 유향 간선으로 입력합니다. 양방향 이동은 두 방향을 각각 적고 출발점과 목표점을 지정합니다.
- 계산하기를 누르면 최단 거리·경로 결과를 확인할 수 있습니다. 아래 고정 예시와 비교할 때는 입력 조건도 같아야 합니다.
| 입력 항목 | 예시 값 | 입력 안내 |
|---|---|---|
| 유향 간선: 출발번호 도착번호 비용 | 1 2 4 1 3 2 3 2 1 2 4 3 3 4 8 | 한 행씩 줄바꿈, 열은 공백 또는 쉼표로 구분합니다. 표 안에서는 천 단위 쉼표를 쓰지 마세요. |
| 노드 수 | 4 | 2~50 정수 · 천 단위 쉼표 사용 가능 |
| 출발 노드 | 1 | 1~50 정수 · 천 단위 쉼표 사용 가능 |
| 목표 노드 | 4 | 1~50 정수 · 천 단위 쉼표 사용 가능 |
| 결과 항목 | 예시 결과 |
|---|---|
| 최단 거리 | 6 |
| 경로 | 1 → 3 → 2 → 4 |
위 표는 고정된 예시입니다. 직접 입력한 값의 결과는 입력란 아래에 표시됩니다. 실제 이용 시에는 아래 계산 방법과 적용 조건을 함께 확인하세요.
계산 방법
Bellman–Ford 방법으로 유향 그래프의 최단 경로를 계산합니다. 출발점에서 도달 가능한 음수 순환이 있으면 계산을 거절합니다.
알아두세요
Bellman–Ford 유향 최단경로입니다. 양방향 간선은 두 방향을 각각 입력하세요. 음수 순환이 있으면 계산하지 않습니다. 입력 범위 안의 모형 계산이며 실제 자료의 가정 충족 여부를 자동 판정하지 않습니다.
자주 묻는 질문
최단 경로에서 음수 비용도 사용할 수 있나요?
Bellman–Ford 방식으로 음수 간선을 처리합니다. 출발점에서 도달 가능한 음수 순환이 있으면 비용을 계속 줄일 수 있어 정상적인 최단 경로 결과를 내지 않습니다.
계산 방식 참고: SciPy 최적화 방법 목록 — 관련 계산 원리 참고
입력·결과 안내 점검: · 생활 계산기