Dijkstra's Algorithm

Problem Definition

• Find the shortest path from a starting vertex to all other vertices.

Assumption

1. The graph is connected.
2. The edge weights are nonnegative.

Methodology

• 처음 노드에서부터 'cloud'(이미 starting vertex로부터 shortest path가 알려진 vertex의 set를 의미한다.)를 확장하여 모든 vertices를 커버한다.
• 시작 노드로부터 가까운 노드들부터 하나씩 해결한다.
• edge를 하나씩 추가한다.
  • Find the path to each vertex one by one.
  • Iteratively expand the set of nodes where the shortest path is known.

---

Bellman-Ford Algorithm

• 다익스트라 알고리즘은 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다.
• 시간 복잡도는 O((n + m)logn))으로, n+m은 adjacent list일 경우에 걸리는 vertex와 edge 탐색 시간, logn은 PQ를 유지하면서 탐색하는 시간을 의미한다.

---

• 반면, 벨만-포드 알고리즘은 매 단계마다 모든 간선을 전부 확인하며 모든 노드간의 최단 거리를 구해나간다.
• 반드시 directed edges를 가정해야 한다! 만약 undirected graph일 경우, 음수 가중치 cycle이 형성될 수도 있기 때문이다.
• 음수 간선이 있어도 최적의 해를 찾을 수 있다.
• 시간 복잡도는 O(nm)으로, 느린 편이다.

procedure

• 전체 노드 개수 - 1 번의 반복을 하는 동안, i번째 iteration에서 i edges를 사용하는 모든 최단 경로를 구한다.

Directed Acyclic Graph (DAG)

Definition

• A digraph that has no directed cycles.

  Digraph : 모든 간선이 방향이 있는 그래프

• Digraph (directed graph) : a graph whose edges are all directed.

Properties

• Each edge goes in one direction.
• Edge (a, b) goes from a to b, but not b to a.
• If G is simple, m <= n(n-1)

  Why? 각 노드별 간선의 갯수가 n-1, n-2, n-3, ..., 1, 0이 되므로, n(n-1)/2이다. 이 때, 방향이 두 가지 존재하므로 2 * n(n-1)/2 = n(n-1)이 최대 간선 갯수가 된다.

Topological Sort in a DAG

Key procedure

1. in-degree가 0인 정점을 큐에 넣는다.
2. 어떤 정점 u를 제거할 때, [u에서 나가는 간선들(out-edges)을 보고], [도착 정점 v의 in-degree를 1씩 감소시킨다].

   이 때, 필요한 연산은

• 정점 u의 out-edges 리스트를 빠르게 조회한다.
• 정점 v의 in-edges는 조회할 필요 없이, in-degree만 1 감소시킨다.

Pseudo Code

ALgorithm TopologicalSort(G)
	H <- G			// Temporary copy of G
    n <- G.numVertices()
    while H is not empty do
    	Let v in H be a vertex with no outgoing edges
        Label v <- n
        n <- n-1
        Remove v from H

DAG-based Shortest Path Algorithm

왜 Dijkstra's alg보다 빠른가?

• 그래프에 사이클이 없고, 엣지가 한 방향으로만 존재하기 때문에. 그런 그래프가 constant를 갖고 있기 때문에.
• Topological Order를 사용할 수 있기 때문에. 덕분에 정점을 단 한 번씩만, 간선을 단 한 번씩만 확인하면 끝난다.
  즉, 우선순위 큐가 필요 없고, 복잡한 relaxation 반복도 필요 없다.

DAG SP와 Topological Sort의 관계

• DAG SP 알고리즘은 위상 정렬이 없으면 아예 성립할 수 없다.
• 즉, DAG 최단 경로 알고리즘은 위상 정렬을 기반으로 만들어진 알고리즘으로, 구조적 기반 <-> 응용 관계이다.
• 위상 정렬이 DAG의 정점들을 정답이 될 수 있는 순서로 정렬해준다.
• DAG-based SP 알고리즘은 그 순서를 이용해 각 정점을 단 한 번만 처리해서 최단 경로를 계산한다.

즉, 위상 정렬이 순서를 만들고, DAG-SP가 그 순서를 이용해 최단 경로를 구한다.