다익스트라, 벨만 포드 알고리즘

ㅤ	다익스트라	벨만포드
사용	양의 간선만 있을 때 최단 거리	음의 간선이 있을 때 최단 거리 음수 사이클 탐지에도 사용
시간복잡도	O(M log N) - M: 간선, N: 노드	O(NM)
ㅤ	음수 가중치가 없다면, 다익스트라가 압도적으로 빠르기 때문에 다익스트라 사용	음수 가중치나 음수 사이클이 있을 때만 사용 권장

다익스트라

최단 거리 테이블을 조금씩 갱신하며 완성해내가는 알고리즘

한 지점에서 다른 지점으로 가는 최단 거리를 구하는 알고리즘
음의 간선이 없을 때 사용 가능

음의 간선을 포함한 그래프에서 최단거리 계산하는 알고리즘

음수 사이클이 존재하는지도 확인 가능