비전공자의 프로그래머 도전기
로그인
비전공자의 프로그래머 도전기
로그인
최단 경로 알고리즘
김찬수
·
2023년 3월 7일
팔로우
0
다익스트라 알고리즘
최단 경로 알고리즘
0
개요
최단 경로는 가중치 그래프에서 두 정점을 연결하는 경로 중 가중치의 합이 최소인 경로를 말한다.
최단 경로를 구하기 위해서는 그래프에 음수인 가중치가 있어서는 안되고, 간선이 없을 경우 무한대 값으로 저장한다.
최단 경로를 구하는 알고리즘에는 다익스트라 알고리즘과 이를 변형 시킨 에이스타 알고리즘이 있다.
다익스트라 알고리즘
다익스트라 알고리즘은 무방향 그래프, 방향 그래프 모두에 적용 가능한 알고리즘이다.
기본 원리는 시작 정점에서 가장 가까운 정점을 선택하여 추가하면서 추가된 모든 정점에 대한 최단 경로를 구해가는 과정이다.
구현
C#으로 구현하면 아래와 같다.
김찬수
프로그래머 지망생
팔로우
이전 포스트
해시 테이블
다음 포스트
문맥 교환 (Context Switching)
0개의 댓글
댓글 작성