🚇 서울 지하철 최단경로 알고리즘 시뮬레이션

개선된 다익스트라 알고리즘: 노드 가중치를 고려한 엣지 라벨링 방식 (실제 서울 지하철 노선도)

0
총 역 수
0
노선 수
0
구간 수

🎯 경로 설정

출발역

도착역

알고리즘 실행

🔬 알고리즘 특징

  • 개선된 방식: 엣지 라벨링
  • 기존 방식: 노드 확장
  • 역 진입/진출 시간 고려
  • 환승 시간 동적 계산
  • 실제 노선 데이터 반영

📌 사용 방법

1. 출발역과 도착역을 선택하세요

2. 알고리즘을 선택하여 실행하세요

3. 비교 버튼으로 두 방식을 비교할 수 있습니다

※ 실제 서울 지하철 1-9호선 데이터 사용

️ 서울 지하철 노선도

1호선
2호선
3호선
4호선
5호선
6호선
7호선
8호선
9호선
T
환승역

📊 결과

🔄 계산 중...

📚 이론적 배경

기존 다익스트라의 한계

  • • 간선에만 가중치 고려
  • • 노드(역) 내부 시간 무시
  • • 환승 시간 정확히 반영 불가
  • • 해결책: 노드 확장 (복잡도 증가)

개선된 알고리즘

  • • 엣지를 라벨링 대상으로 변경
  • • 노드 확장 불필요
  • • 동적 환승 시간 계산
  • • 시간 복잡도: O(m log m)