The Shortest Path

The shortest path problem aims to find the path between two vertices (or nodes) where the sum of the weights of each edge is minimized.

Floyd Algorithm

An algorithm to find the shortest distances between all pairs of vertices.

It works well even if the edge value is negative, but problems arise if there's a negative cycle.

Assuming there are V vertices, updates occur over V stages. At each k=1,2,3,…,V step, all $V^2$ D[s][t] values are compared with the D[s][k]+D[k][t] value. Hence, the time complexity of the Floyd algorithm is $O(V^3)$ . The rationale behind this algorithm can be mathematically proven rigorously through an inductive argument.

Implementation

The triple for-loop runs. When implementing the Floyd algorithm, think of i as the starting point and j as the endpoint, with k, i, and j being the values in the for-loops. It's crucial to remember that the element to be used as a detour in the middle should be on the outermost loop.

Instead of making assignments every time, using if(d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j] is more time-efficient, only making assignments when necessary. While the difference might seem negligible in problems where assignments occur around 100,000 or 1,000,000 times, in situations like the Floyd algorithm where there are a billion assignments, the difference becomes quite significant. In this problem, with a maximum of 100 vertices, the difference isn't much, but in a graph with 1,000 vertices, this improvement can reduce time from approximately 950ms to around 700ms.

This not only applies to the Floyd algorithm but also to typical dynamic programming problems and other situations where frequent assignments occur. This type of improvement is often referred to as constant-time optimization.

Pseudocode

# let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)

for each edge (u, v) do
    dist[u][v] ← w(u, v)  # The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
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

Path reconstruction pseudocode

# let dist be a |V| X |V| array of minimum distances initialized to ∞(infinity)
# let prev be a |V| X |V| array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction() is
    for each edge (u, v) do
        dist[u][v] ← w(u, v)  # The weight of the edge (u, v)
        prev[u][v] ← u
    for each vertex v do
        dist[v][v] ← 0
        prev[v][v] ← v
    for k from 1 to |V| do    # standard Floyd-Warshall implementation
        for i from 1 to |V|
            for j from 1 to |V|
                if dist[i][j] > dist[i][k] + dist[k][j] then
                    dist[i][j] ← dist[i][k] + dist[k][j]
                    prev[i][j] ← prev[k][j]

Reference: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Dijkstra's Algorithm

An algorithm to find the shortest distance from one starting point to all other vertices.

Dijkstra's algorithm is a representative of greedy algorithms that always select the shortest path around a node. It uses BFS when exploring the node's surroundings.

Although the Floyd algorithm works fine even if the edge value is negative, problems arise if there's a negative cycle. However, the Dijkstra algorithm cannot be used at all if there's an edge with a negative weight. If you want to find the shortest distance from one starting point to all other vertices and there's an edge with a negative weight, you can use the Bellman-Ford algorithm.

As an example of path-finding algorithms, some of you might have heard of the A* (A star) algorithm. However, A* is an approximate algorithm useful when you don't need 100% accurate shortest distances, like in navigation, or when there are too many vertices making it impractical to use Dijkstra. In most problem-solving situations, we need an accurate answer, not an approximation. So, you don't really need to know the A* algorithm.

Pseudocode

function Dijkstra(Graph, source):
  
  for each vertex v in Graph.Vertices:
      dist[v] ← INFINITY
      prev[v] ← UNDEFINED
      add v to Q
  dist[source] ← 0
  
  while Q is not empty:
      u ← vertex in Q with min dist[u]
      remove u from Q
      
      for each neighbor v of u still in Q:
          alt ← dist[u] + Graph.Edges(u, v)
          if alt < dist[v]:
              dist[v] ← alt
              prev[v] ← u

  return dist[], prev[]

Using a priority queue

function Dijkstra(Graph, source):
  dist[source] ← 0                           # Initialization

  create vertex priority queue Q

  for each vertex v in Graph.Vertices:
      if v ≠ source
          dist[v] ← INFINITY                 # Unknown distance from source to v
          prev[v] ← UNDEFINED                # Predecessor of v

     Q.add_with_priority(v, dist[v])


 while Q is not empty:                      # The main loop
     u ← Q.extract_min()                    # Remove and return best vertex
     for each neighbor v of u:              # Go through all v neighbors of u
         alt ← dist[u] + Graph.Edges(u, v)
         if alt < dist[v]:
             dist[v] ← alt
             prev[v] ← u
             Q.decrease_priority(v, alt)

 return dist, prev

Reference: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Last updated 2 years ago