Relaxation

Each point has a known distance so far, if a vertex + distance to a particular point is shorter than the known distance of the point, update it. if (d[v] > d[u] + w(u, v)) d[v] = d[u] + w(u, v)

Dijkstra Algorithm

Extract min from the priority queue and relax its surroudning vertexes.

The priority queue is implement with Fibonacci heap

  Initialize-single-source(G, S) // set all distance to infinity
  S = {} // path 
  Q = G.V
  while (Q is not empty)
    u = EXTRACT-MIN(Q)
    S union u
    for each vertex v in adj[u] // total E times
      RELAX(u, v, w)

Running time

while loop executes V times EXTRACT-MIN take O(log V) decrease key operation O(1) with total edges E times

Overall Running time: O(V log V + E)

Naive method: O(V^2 + E), (linear search for EXTRACT-MIN)

Limitation

Only applicable for graphs with positive edge

Bellman-Ford Algorithm

Suppose a path from source to destination at most contains V - 1 edges It basically try to relax every edges in the path until you reach the destination It is based on dynamic proramming, but without a successor table of each vertex. d[i, v] = d[i - 1, v] d[i, v] = min(d[i, v], min(i - 1, u) + w(u, v))

for i = 1 to V - 1
  for each vertex u 
  if (d[u] is updated)
    for each vertex v in adj[u]
       if (d[v] > d[u] + w(u, v))
          d[v] = d[u] + w(u, v)
          successor = u
  if no value is change, break

It can also detect negative cycle

  for each edge(u, v)
    if (d[u] + w(u, v) < d[v])
       "negative cycle detected !!"

Running time analysis

Simply O(VE), memory space (V + E)