Single-source shortest paths

If the graph contains no negative-weight edges, we can apply the GreedyMethod

Dijkstra’s algorithm:

Dijkstra(G,w,s):
  Set d[s] = 0 and set d[v] = +infinity for all v != s.
  Add all the vertices to Q.
  while Q is not empty:
    u = EXTRACT-MIN(Q)
    for each each uv:
      d[v] = min(d[v], d[u] + w(u,v))
  return d

Note: Time complexity: O(v^2)

BellmanFord’s algorithm:

if the graph contains negative edges and under the assumption that there are no negative-weight cycles in the graph

BellmanFord(G,s,w):
  Set d[s] = 0 and set d[v] = +infinity for all v != s.
  // Relax all edges |V| - 1 times. A simple shortest path from src to any other vertex can have at-most |V| - 1 edges
  for i = 1 to V-1 
    for each each edge uv in G:
      d[v] = min(d[v], d[u] + w(u,v))
  return d

Note: Time complexity: O(VE)

---

All-pairs shortest paths problem

FloydWarshall algorithm

finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles)

FloydWarshall(w):
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
  for each vertex v
    dist[v][v] ← 0
  for each edge (u,v)
    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
  for k from 1 to |V|
    for i from 1 to |V|
      for j from 1 to |V|
        if dist[i][j] > dist[i][k] + dist[k][j] 
          dist[i][j] ← dist[i][k] + dist[k][j]
        end if

Note: Time complexity: Θ(v^3)

Ref: https://www.cs.yale.edu/homes/aspnes/pinewiki/ShortestPath.html
Ref: https://zh.wikipedia.org/wiki/Floyd-Warshall%E7%AE%97%E6%B3%95