# Shortest Path Algorithm

# 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)