무방향 뿐 아니라 방향 그래프에서도 정의그래프에 음의 무게를 가진 싸이클 이 있거나, 무방향 그래프에 음의 무게를 가진 간선 이 있으면 부정.최단 경로 트리는 루트트리음의 무게를 가진 간선이 없는 그래프 Dijkstra , O(mlog(n)) || O(n^2)음의 무게