Single-Source Shortest Path Algorihtms

Bellman-Ford Algorithm

• negative edge가 포함된 경우에 사용
• negative-weight cycle이 있는 경우에 확인 가능

bellman_ford(G, w, s):
    G.init(s)
    for i = 1 to |G.V|-1:
        for (u,v) in G.E:
            relax(u,v,w)
    for (u,v) in G.E:
        if v.d > u.d + w(u,v):
            return False
    return True

• relaxation의 특성 상 $V-1$번 돌고 나면 더 이상 weight update가 가능하지 않아야 한다.
  • 그 이후에 한 번 더 relaxtion으로 update될 수 있다면 negative cycle이 존재함을 의미한다.
• Time Complexity: $O(VE)$

Python Code

boj 11657

Dijkstra’s algorithm

• weighted, directed graph에서 사용
• 모든 edge가 nonnegative여야 함.
• Bellman-Fold보다 빠름.
• priority-queue 사용

dijkstra(G, s):
    G.init(s)
    visited = set()
    pq = G.V
    while pq:
        u = pq.pop
        visited.add(u)
        for v in G.adj(u)
            relax(u,v,w)

• Procedure
  • 처음에 모두 inf로 초기화
  • 매 iteration마다 방문하지 않은 vertex 중 minimum cost 선택
  • 해당 node 기준으로 adj node들 relaxation
  • Q empty까지 반복
• Time Complexity: $O(V\lg V +E\lg V ) = O(E\lg V)$
  • pq pop $O(V\lg V)$
  • relax하면서 pq에 넣기 $O(E\lg V)$

Python Code

boj 1753

All-pairs Shortest Path Algorithms

Floyd-Warshall Algorithm

• all-pair shortest path 계산
• negative weight cycle이 없는 경우