• 다익스트라 알고리즘

그래프에서 시작 정점을 기준으로 다른 모든 정점까지 최단 거리를 찾는 알고리즘이다. 음의 가중치를 갖는 간선이 없는 경우에 사용 가능하며, 모든 정점은 방문하기 전까지 무한대 값을 갖는다. 시작 정점으로부터 연결되어 있는 정점을 방문하며 시작 정점으로부터의 거리를 저장하고, 더 짧은 거리를 갱신한다.

• 벨만포드 알고리즘

그래프에서 시작 정점을 기준으로 다른 모든 정점까지 최단 거리를 찾는 알고리즘이다. 음의 가중치를 갖는 간선이나, 음의 사이클이 있는 경우에도 사용 가능하다. 음의 간선을 고려하여 모든 경우의 수를 탐색하기 때문에 다익스트라 알고리즘보다 느리다. 모든 간선을 탐색하면서, 시작 정점에서 다른 정점까지 거리가 INF가 아니라면 거리를 갱신한다.

• 플로이드워셜 알고리즘

그래프에서 모든 정점 쌍에 대 최단 거리를 한번에 찾는 알고리즘이다. 음의 가중치를 갖는 간선이 있어도 사용할 수 있지만, 음의 사이클이 있는 경우 사용할 수 없다. 모든 노드에 대해 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문에 2차원 배열을 이용한다. 해당 노드를 거쳐 가는 경우를 고려하여 최단 거리를 갱신한다.