11.3.2 다익스트라 알고리즘 소스 코드

다음은 앞에서 구현한 다익스트라 알고리즘 코드입니다.

다익스트라 알고리즘은 인접행렬로 표현하는 것은 다루지 않았습니다. 앞에서 다룬 문제들을 인접 행렬로 소개한 것도 있고 비교적 구현이 단순하지만 실제 정점의 개수가 많으면 메모리 효율과 성능이 떨어지는 문제점을 갖고 있습니다. 이러한 이유와 더불어 그리 어렵지 않게 인접 행렬로 구현한 코드는 찾을 수 있기에 과감히 생략하였습니다.

위 코드는 약간의 코드 변경으로 벨만 포드 알고리즘으로 변경이 가능합니다. 경로 값만 음수로 전달하면 그대로 적용할 수 있으니 한 번 확인해 보시기 바랍니다.

15