Shortest Path Problem

Introduction

• In graph theory, the shortest path problem is the problem of finding a path between two vertices/nodes (as source and destination) in a graph such that the sum of the weights/costs of its constituent edges route is minimized.
• The shortest path problem is considered as –
  • The single-pair shortest path problem: It includes –
    • The single-source shortest path problem, in which we have to find the shortest paths from a source vertex (v) to all other vertices in the graph.
    • The single-destination shortest path problem, in which we have to find the shortest paths from all vertices in the directed graph to a single destination vertex v. This can be reduced to the single-source shortest path problem by reversing the arcs in the directed graph.
  • The all-pairs shortest path problem, in which we have to find the shortest paths between every pair of vertices (v, v’) in the graph.

Definition

• The shortest path problem is the problem of finding a path between two vertices/nodes between the source & destination node in a graph such that the sum of the weights of its constituent edges is minimized.

Characteristics

• The shortest path problem is applied with a Directed, Undirected or Mixed graph.
• Here, the shortest path in a graph from one vertex to another is the least number of edges or least total weight, etc.

Use/Application

• To find directions between physical locations i.e. in web mapping such as in MapQuest or Google Maps.
• In the transport sector for Vehicles routing problems.
• To optimize the various problems.
• In Telecommunication sectors.
• To sort out the logistics problems.
• Critical path analysis in project management.

Algorithms of Shortest Path Problem

• There are two famous algorithms to find out the shortest path problems. These are –

Dijkstra’s Algorithm (Single Source Shortest Path[SSSP] Problem)

Introduction

• This algorithm was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
• The Single-Source Shortest Path (SSSP) problem consists of finding the shortest paths between a given vertex (v) and all other vertices in the graph. 

Definition

• Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a non-negative weighted, directed, or non-directed graph.

Characteristics

• Dijkstra’s algorithm solves the single-source shortest path problem with non-negative/positive edge weight or costs only.
•  It is a type of greedy algorithm.
• Dijkstra’s algorithm works on the principle of BFS with a priority queue.

Bellman-Ford Algorithm (Single Source Shortest Path[SSSP] Problem)

Definition

• The Bellman-Ford algorithm is a popular algorithm used to find the shortest path in a weighted directed graph from a single source vertex to all other vertices. It can handle graphs even with negative weight edges but detects negative cycles.

Characteristics

• Bellman-Ford algorithm solves the single-source shortest path problem with both non-negative/positive or negative edge weight or cost. 
• Bellman-Ford algorithm can handle graphs with both directed and undirected edges.
• The algorithm works by iteratively relaxing the edges of the graph. Relaxing an edge means updating the distance to the destination vertex if a shorter path is found. The algorithm repeatedly relaxes all edges in the graph until no further improvements can be made.
• The time complexity of the Bellman-Ford algorithm is O(|V| * |E|), where |V| is the number of vertices and |E| is the number of edges in the graph.
• Bellman-Ford algorithm can handle graphs with negative edge weights and can also detect negative-weight cycles.
• Bellman-Ford algorithm is less efficient than some other algorithms, such as Dijkstra’s algorithm, for graphs without negative edge weights.
• Steps of the Bellman-Ford algorithm:-

  • Initialize the graph:

    • Set the distance of the source vertex to 0.
    • Set the distance of all other vertices to infinity.
    • Also, create an array to store the predecessor of each vertex.

  • Iterate over all edges |V| – 1 time, where |V| is the number of vertices in the graph.

    • For each edge (u, v) with weight w, if the distance to v can be improved by taking the path through u (distance[u] + w < distance[v]), update the distance[v] to the new shorter distance.

  • Check for negative-weight cycles:

    • Iterate over all edges again and if any distance can still be improved, it means the graph contains a negative-weight cycle. This condition is used to detect and report the presence of negative cycles in the graph.

    • If no negative cycles are detected, the algorithm terminates, and the distances and predecessors represent the shortest paths from the source vertex to all other vertices.

  • At the end of the algorithm, the distance array will contain the shortest distances from the source vertex to all other vertices in the graph. If there are no negative-weight cycles, these distances will be the shortest paths.

Floyd-Warshall Algorithm (All Pair Shortest Path/APSP Problem)

• The Floyd-Warshall algorithm is an efficient algorithm used to find the shortest path between all pairs of vertices in a weighted directed graph, including graphs with negative edge weights.
• The Floyd-Warshall algorithm supports the All-Pairs Shortest Path (APSP) problem consists of finding the shortest path between all pairs of vertices in the graph.
• It works based on the concept of dynamic programming.
• It works for both non-negative/positive or negative edge weight or cost. 
• The time complexity of the Floyd-Warshall algorithm is O(V³), where V is the number of vertices in the graph. The space complexity is O(V²) to store the distance and “next” matrices.
• The Steps of the Floyd-Warshall algorithm are:
  • Initialize a matrix, called the distance matrix, with the initial distances between vertices. If there is an edge between vertices u and v, set the corresponding entry in the matrix as the weight of that edge. If there is no edge, set the entry to infinity. Additionally, set the diagonal entries of the matrix to 0.
  • Perform a triple nested loop that iterates over all vertices in the graph. In each iteration, consider each pair of vertices (u, v) and check if the path from u to v can be improved by going through a third vertex, let’s call it k. The distance matrix entry for the pair (u, v) is updated as the minimum of the current distance and the sum of the distance from u to k and the distance from k to v.
  • After the triple nested loop completes, the distance matrix will contain the shortest path distances between all pairs of vertices in the graph.