Shortest path in an unweighted graph

Graph For Faang

Crispy Things in Graph

Shortest Path in Graph

Mastering Graph Algorithm

Before we dive into the topic, let’s first understand what the shortest path is. After that, we’ll discuss why learning its algorithms is important.

What is the Shortest Path?

What is the Shortest Path in a Graph?

The shortest path means the path between two nodes in a graph that has the smallest possible total weight or cost among all the available paths.

So, this is a concept that is widely used in graph theory and it also plays a crucial role in solving various real-world problems, such as network routing, navigation systems, and optimization challenges.

For example, to find the shortest path in a graph from the source vertex V1 to the target vertex V5 (as illustrated in the diagram below), we need to explore all possible paths to find the smallest one.

In the above picture of a graph, you do not see weights or similar attributes because the diagram represents a graph that consists of nodes (or vertices) and edges.

Edges can have weights or costs, which typically represent distances, times, or other measurable metrics.

The other possible graphs that can be used to find the shortest path are:-

1. Unweighted Graph

An unweighted graph means that no weight or cost is assigned to the edges.

In the above picture of graph, we can see that no weights or costs are given for the edges.

Now, the question is, How do we find the distance between two nodes if weight or cost is not given?

So, What is the weight or cost of edges in an unweighted graph?

Without weights or costs, it would not be possible to find the distance between two nodes.

By default, we consider the weight or cost of edges in an unweighted graph to be 1. This means the distance between two neighboring nodes is treated as 1.

2. Weighted Graph

A weighted graph means that each edge is assigned a specific weight or cost.

In the above picture of graph, we can see that weights or costs are given for the edges.

So, What is the significance of weights or costs in a weighted graph?

The significance of weights or costs in a weighted graph is very important, because

These weights or costs represent the distance, cost, or any other metric between two connected nodes.

We will use this weight to find the exact distance or cost between nodes.

The presence of weights in the graph, makes easy choice to choose the path and so it enables more complex operations such as finding the shortest path.

3. Negative Weighted Graph (Bellman-Ford Algorithm)

A negative weighted graph means that some edges are assigned negative weights or costs.

The weights or costs can be negative weight.

In the above picture of graph, we can see that certain edges have negative weights.

What is the significance of negative weights in a graph?

Negative weights can represent scenarios such as discounts, penalties, or reductions in cost. However, they can also lead to complexities in finding the shortest path, as cycles with negative weights may result in infinite reductions.

The Bellman-Ford Algorithm is specifically designed to handle graphs with negative weights. It helps compute the shortest paths from a source node to all other nodes, even in the presence of negative edge weights, given there are no negative weight cycles.

Key Points to Keep in Mind:

A weighted graph can contain both negative and non-negative weights.

What do negative and non-negative weights in a weighted graph?

Non-negative weights (such as 0 or positive values) are very common.

Non-negative weights represent metrics in the graph problems for example: distance, cost, or time, where negative values don’t make logical sense.

On the other hand, negative weights are used in scenarios where a decrease or benefit is represented, such as discounts or reductions.

While the graphs with non-negative weights are easier to solve the problem with algorithms like Dijkstra’s Algorithm.

But, the presence of negative weights requires specialized algorithms like the Bellman-Ford Algorithm.

So that the algorithm can compute shortest paths even when negative weights exist in the graph.

Since if there are no negative weight cycles (which could cause infinite reductions).

In this article, we will focus specifically on the topic of the Shortest Path in an Unweighted Graph. Additionally, we will provide brief and concise notes on the variations of shortest path algorithms for your reference.

Types of Shortest Path Algorithms

1. Single-Source Shortest Path (SSSP)

The Single-Source Shortest Path(SSSP) is a very classical algorithm in graph theory.

This SSSP is used to find the shortest path from a single source vertex to all other vertices in a weighted graph.

Actully, the main aim of this SSSP is to minimize the sum of weights or costs of the edges in the paths.

The shortest path from every vertex (v) to a specific destination vertex (t).

We can achieve the shortest Path by reversing the direction of each edge in the graph,

and so this problem can be simplified into a single-source shortest path problem.

It means that instead of solving the original problem of finding the shortest path to a destination vertex (t) from every other vertex,

You can simplify it by reversing the directions of all the edges in the graph.

This change simplifies the problem into finding the shortest path from (t) to all other vertices.

Once the directions are reversed, you can treat ( t ) as the source of a single-source shortest path problem,

which is a well-studied problem with efficient algorithms like Dijkstra's or Bellman-Ford.

Basically, you turn a "shortest path to (t)" problem into a "shortest path from (t)" problem by reversing the graph.

The Single-Source Shortest Path problem involves finding the shortest paths from a single source node to all other nodes in a graph.

This is commonly used in navigation, network optimization, and other graph-based problems.

Key Features of Single-Source Shortest Path:

Source Node: The node from which all shortest paths are computed.
Graph Types:
- Unweighted Graph: All edges have equal weight.
- Weighted Graph: Edges have different weights.
Shortest path varies based on edge weights.

Finds shortest paths from a single source to all other vertices in a weighted graph.

Dijkstra: For non-negative weights
Bellman-Ford: Handles negative weights, detects cycles
BFS: For unweighted graphs

2. Single-Pair Shortest Path (SPSP)

The single-pair shortest path (SPSP) problem is used to find the shortest path between two specific vertices(nodes) in a graph.

The single-pair shortest path (SPSP) problem is the task of finding the shortest path between two specific vertices, say A and Z, in a weighted graph.

It focuses on finding the shortest path between a specific source and destination vertex using algorithms like Dijkstra or BFS (optimized for single-pair scenarios).

Does SPSP Always Require Solving All-Pairs Shortest Paths?

No, SPSP does not always require solving the single-source shortest path (SSSP) problem (finding shortest paths from A to all other vertices) or the all-pairs shortest paths (APSP) problem.

Some algorithms can terminate early when they find the shortest path to the destination Z, avoiding unnecessary computations for other vertices.

Dijkstra’s Algorithm (Optimized for SPSP):-

Dijkstra’s algorithm is commonly used for finding shortest paths from a source to all vertices in a graph. However, when applied to SPSP, it can terminate as soon as the shortest path to the destination Z is found.

This works because Dijkstra's algorithm processes vertices in increasing order of distance from the source, ensuring that once a vertex is processed, its shortest path is guaranteed.

Thus, it does not compute the shortest path to every vertex unless necessary.

A* Search Algorithm:

A* is specifically designed for SPSP and uses a heuristic to guide the search toward the destination Z.

By incorporating an estimated cost-to-goal (heuristic function), A* avoids exploring parts of the graph that are unlikely to be on the shortest path.

This can significantly reduce the number of vertices visited compared to Dijkstra’s algorithm.

Bidirectional Search:-

Bidirectional search works by simultaneously performing a forward search from A and a backward search from Z, meeting somewhere in the middle.

This can be more efficient than searching the entire graph from A to Z.

Algorithms like A* or Dijkstra can prune unnecessary computations once they reach Z, leveraging specific properties (like graph structure or heuristics) to focus on the relevant portion of the graph.

SPSP finds the shortest path between two specific vertices (e.g., A and Z) in a weighted graph using algorithms like Dijkstra, BFS, or A*.

Does SPSP Require Solving All-Pairs or Single-Source Shortest Paths?

No. SPSP algorithms can terminate early upon finding the path to the destination, avoiding unnecessary computations for other vertices.

Dijkstra’s Algorithm (SPSP Optimization): Processes vertices in order of distance, ensuring the shortest path to Z is found without computing paths to all vertices.

A* Algorithm: Uses heuristics to guide the search toward Z, reducing unnecessary exploration and improving efficiency compared to Dijkstra’s.

Bidirectional Search: Searches forward from A and backward from Z, meeting in the middle to minimize the search space.

Finds shortest path between two nodes.

A*: Uses heuristics for efficiency
Bidirectional Search: Reduces search space

3. All-Pairs Shortest Path (APSP)

The All Pairs Shortest Path (APSP) algorithm calculates the shortest (weighted) path between all pairs of nodes.

This algorithm is more efficient than calling the Single Source Shortest Path algorithm for every pair of nodes in the graph.

Floyd-Warshall Algorithm: The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes in a graph. It works well for dense graphs.
Johnson's Algorithm: Johnson's algorithm uses a technique of assigning an integer to each vertex. For two vertices, u and v, with an edge (u -> v), the edge weight is adjusted by (C[u] - C[v]), where C[u] and C[v] are the integers assigned to u and v, respectively.

It is efficient for sparse graphs, as it combines Bellman-Ford and Dijkstra’s algorithms.

Sparse Graph: A sparse graph is one with few edges, typically close to the minimum needed to maintain connectivity. In a connected sparse graph, the number of edges is roughly equal to the number of vertices.

For example, a graph with 5 vertices (A, B, C, D, E) could have just enough edges to connect the vertices, such as (A to B, B to C, C to D, D to E). This graph has 4 edges, close to the minimum required to keep all vertices connected.

Calculates shortest paths between every pair of nodes.

Floyd-Warshall: Efficient for dense graphs
Johnson’s Algorithm: Optimized for sparse graphs

4. Specialized Variations

A* Algorithm: Uses heuristics to find the shortest path efficiently, often used in navigation systems.
Bi-Directional Search: Searches from both source and target simultaneously to find the shortest path faster.
ALT (A*, Landmarks, and Triangle inequality): Combines A* with precomputed landmarks for faster pathfinding.

5. Pathfinding in Weighted Graphs

Uniform Cost Search (UCS): Similar to Dijkstra’s but focuses on cost rather than distance.

6. Pathfinding in Graphs with Constraints

Constrained Shortest Path: Finds paths that satisfy additional constraints (e.g., time or capacity limits).

7. Dynamic Graph Algorithms

Handle scenarios where the graph changes over time (e.g., edge additions, deletions, or weight updates).
Dynamic Dijkstra: Efficiently recalculates paths for small changes.

8. Approximation and Heuristic-Based Algorithms

Greedy Best-First Search: Faster but not guaranteed to find the shortest path unless combined with heuristics.
Simulated Annealing: For approximating paths in complex graphs.

9. Specialized Applications

Network Flow Algorithms: E.g., Ford-Fulkerson, used for flow optimization.
Transit Node Routing: Optimized for very large graphs like road networks.

10. Graph Type Variants

Unweighted Graphs: BFS is most efficient.
Directed Acyclic Graphs (DAGs): Use topological sorting followed by relaxation.

Shortest Path in an Unweighted, Undirected Graph

Example 1

Input:

V = 6, E = 7, S = 0, D = 5, edges[][] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}, {2, 5}}

Output: 0 2 5

Explanation: The shortest path is 0 -> 2 -> 5.

Example 2

Input:

V = 5, E = 6, S = 0, D = 4, edges[][] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {0, 3}, {1, 4}}

Output: 0 3 4

Explanation: The shortest path is 0 -> 3 -> 4.

Example 3

Input:

V = 7, E = 9, S = 3, D = 6, edges[][] = {{0, 1}, {0, 2}, {1, 3}, {3, 4}, {4, 5}, {5, 6}, {2, 6}, {1, 5}, {3, 6}}

Output: 3 6

Explanation: The shortest path is 3 -> 6.

Example 4

Input:

V = 9, E = 11, S = 0, D = 8, edges[][] = {{0, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 6}, {5, 7}, {6, 8}, {3, 6}, {2, 5}, {4, 7}}

Output: 0 2 4 6 8

Explanation: The shortest path is 0 -> 2 -> 4 -> 6 -> 8.

Example 5

Input:

V = 4, E = 4, S = 0, D = 3, edges[][] = {{0, 1}, {1, 2}, {2, 3}, {0, 3}}

Output: 0 3

Explanation: The shortest path is 0 -> 3.

Shortest Path in an Unweighted Graph

The shortest path problem is a common scenario in many real-world applications, such as navigation systems, network routing, and game development.

In an unweighted graph, the cost of moving from one vertex to another is uniform, meaning it takes exactly one edge traversal regardless of the actual distance.

Algorithm Overview

For an unweighted graph, the most efficient way to find the shortest path is to use the Breadth-First Search (BFS) algorithm.

BFS explores all neighbors at the current depth level before moving on to nodes at the next depth level. This guarantees the shortest path in terms of edge count.

Steps to Solve

Create a graph using an adjacency list representation.
Maintain a Queue to process nodes level by level.
Keep track of visited nodes to avoid processing them multiple times.
Store the distance of each node from the source in a distance[] array.
Perform BFS starting from the source node and update distances for each neighbor.

Java Implementation


import java.util.*;

public class ShortestPathUnweightedGraph {
    // Method to add edges to the graph
    public static void addEdge(List<List<Integer>> adjList, int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u); // Since the graph is undirected
    }

    // BFS-based shortest path algorithm
    public static int[] shortestPath(List<List<Integer>> adjList, int src, int n) {
        int[] distance = new int[n];
        Arrays.fill(distance, -1); // Initialize distances as -1 (unreachable)
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(src);
        distance[src] = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int neighbor : adjList.get(node)) {
                if (distance[neighbor] == -1) { // If not visited
                    queue.add(neighbor);
                    distance[neighbor] = distance[node] + 1;
                }
            }
        }

        return distance;
    }

    public static void main(String[] args) {
        int n = 7; // Number of nodes
        List<List<Integer>> adjList = new ArrayList<>(n);
        
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        // Add edges
        addEdge(adjList, 0, 1);
        addEdge(adjList, 0, 2);
        addEdge(adjList, 1, 3);
        addEdge(adjList, 1, 4);
        addEdge(adjList, 2, 5);
        addEdge(adjList, 3, 6);

        // Find shortest paths from source (node 0)
        int src = 0;
        int[] distances = shortestPath(adjList, src, n);

        // Print distances
        System.out.println("Shortest distances from node " + src + ":");
        for (int i = 0; i < n; i++) {
            System.out.println("Node " + i + ": " + distances[i]);
        }
    }
}

Explanation of the Code

The graph is represented using an adjacency list, which is memory-efficient for sparse graphs.
The addEdge method creates a bidirectional edge between two nodes, as the graph is undirected.
The BFS traversal starts from the source node, updating distances for each unvisited neighbor.
The distance array keeps track of the shortest distance from the source to every other node. Unreachable nodes remain at their initialized value of -1.

Sample Input and Output

Consider the following graph:

Nodes: 0, 1, 2, 3, 4, 5, 6
Edges: (0-1), (0-2), (1-3), (1-4), (2-5), (3-6)

Output:

Shortest distances from node 0:
Node 0: 0
Node 1: 1
Node 2: 1
Node 3: 2
Node 4: 2
Node 5: 2
Node 6: 3

Complexity Analysis

Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V) for the distance array and the queue.

Applications

Social networks: Finding the shortest chain of friends connecting two people.
Routing algorithms: Finding the minimum number of hops in a network.
Game AI: Calculating the shortest path for characters.

Understanding this fundamental algorithm equips you with the tools needed to tackle more complex graph-related problems like weighted shortest path (Dijkstra's algorithm) or finding paths in directed graphs.