Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Variants
3.
Shortest Path: Existence
4.
Algorithm
5.
Frequently Asked Questions
5.1.
Can Dijkstra's algorithm be used for graphs with negative weights?
5.2.
How does the Bellman-Ford algorithm handle negative cycles?
5.3.
Is Breadth-First Search (BFS) enough for finding the shortest path in all types of graphs?
6.
Conclusion
Last Updated: Mar 30, 2024
Easy

Single Source Shortest Path

Author Sinki Kumari
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Single Source Shortest Path (SSSP) is an important concept in computer science, particularly within graph theory. It focuses on identifying the most efficient route from a specific starting node to all other nodes within a graph. This is similar to finding the quickest paths from your home to various destinations in a city, ensuring each journey is the shortest possible. 

Single Source Shortest Path

In this article, we will learn the fundamentals of SSSP, look into different scenarios, and present practical code examples. 

Variants

When we talk about finding the shortest path in a graph, it's not a one-size-fits-all kind of deal. Depending on the specifics of the graph and what we're trying to achieve, we might have to choose a different approach. Let's break down the main flavors of this problem.

First off, we've got what's called the Unweighted Shortest Path. This is where all edges in the graph are considered equal. Imagine a network of roads with no traffic lights or speed limits; every road is just as good as the next. For these cases, a simple algorithm like Breadth-First Search (BFS) does the trick. It's like checking all the roads that directly connect to your starting point, then all the roads connecting to those roads, and so on, until you've reached your destination.

On the other side, we have the Weighted Shortest Path. Here, each edge has a "weight" or cost associated with it. This could represent distance, time, or any other metric that matters to you. Navigating a weighted graph is a bit like planning a trip when some roads are faster but longer, while others are short but slow. For these situations, algorithms like Dijkstra's or Bellman-Ford come into play, helping us balance the cost and find the most efficient path.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Shortest Path: Existence

Before we find the shortest path, it's crucial to understand that sometimes, a path might not exist at all, or there might be paths that go on indefinitely (think of a loop that keeps going round & round). So, how do we figure out if a shortest path exists?

For unweighted graphs, if there's a way to get from one node to another, there's definitely a shortest path. This is because every edge is equal, so the shortest path is simply the one with the fewest edges. We can use the Breadth-First Search (BFS) algorithm to explore the graph from the source node and easily find this path.

Now, when it comes to weighted graphs, things get a bit more complicated. If the graph has positive weights only, then algorithms like Dijkstra's can find the shortest path efficiently. However, if the graph includes negative weights, we have to be careful. Negative weights can lead to what's called a "negative cycle." This is a loop where the total sum of the edge weights is negative, meaning the more you travel through it, the less the total cost becomes. This makes the concept of a "shortest path" meaningless, as you could theoretically reduce the path cost indefinitely by looping.

To handle negative weights and detect negative cycles, we use the Bellman-Ford algorithm. This algorithm can process graphs with negative weights and also report if a negative cycle is present, which would make finding the shortest path impossible.

Algorithm

When it comes to finding the shortest path in a graph, the algorithm you choose is key. Each algorithm has its own strengths & is suited for different types of graphs. Let's look into two major ones: Dijkstra's Algorithm & Bellman-Ford Algorithm.

Dijkstra's Algorithm is your go-to for weighted graphs without negative weights. It's efficient & works by gradually determining the shortest path to each node from the starting node. It keeps track of two main things for each node: the current shortest distance from the start node & whether we've locked in the shortest path to that node.

Here's a simple breakdown of how Dijkstra's works:

  • Initialize all node distances as infinity, except for the start node, which is set to 0.
     
  • Set the start node as the current node.
     
  • For the current node, consider all of its neighbors. Update their distances to the minimum of their current distances or the distance to the current node plus the edge weight.
     
  • Mark the current node as visited. A visited node will not be checked again.
     
  • Select the unvisited node with the smallest distance as the next "current node" & repeat the process.
     

Continue until all nodes are visited or the smallest distance among the unvisited nodes is infinity (which means the remaining nodes are not reachable).

import heapq
def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
        while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)       
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
        return distances


Bellman-Ford Algorithm, on the other hand, is the algorithm you turn to when your graph might have negative weights. It can handle these negative weights & even detect negative cycles in the graph. It works by relaxing all the edges in the graph repeatedly, updating the shortest path to each vertex if a shorter path is found.

Here's a concise explanation of Bellman-Ford:

  • Initialize the distances to all nodes as infinity, except the start node, set to 0.
     
  • For each edge in the graph, if the distance to the target node can be shortened by taking the edge, update the distance to the target node.
     
  • Repeat the above step for all nodes, (number of nodes - 1) times.
     
  • Check for negative cycles by going through all edges again. If any distance can be shortened, there's a negative cycle.
     
def bellman_ford(graph, start):
    distance = {vertex: float('infinity') for vertex in graph}
    distance[start] = 0

    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                if distance[vertex] + weight < distance[neighbor]:
                    distance[neighbor] = distance[vertex] + weight

    # Check for negative cycles
    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if distance[vertex] + weight < distance[neighbor]:
                print("Graph contains a negative cycle")
                return None

    return distance

Frequently Asked Questions

Can Dijkstra's algorithm be used for graphs with negative weights?

No, Dijkstra's algorithm doesn't work properly if the graph has negative weight edges. It's because the algorithm assumes that adding more to the path will not make it shorter, which isn't true for negative weights.

How does the Bellman-Ford algorithm handle negative cycles?

Bellman-Ford algorithm can detect negative cycles by checking for a condition where the distance to a node can be further reduced even after (number of nodes - 1) iterations. If such a condition is found, it indicates the presence of a negative cycle.

Is Breadth-First Search (BFS) enough for finding the shortest path in all types of graphs?

BFS is suitable for finding the shortest path in unweighted graphs, where the length of the path is measured by the number of edges. However, for weighted graphs, especially those with positive weights, other algorithms like Dijkstra's are more efficient.

Conclusion

In this article, we learned the concept of the Single Source Shortest Path, exploring its various ways. Starting with a fundamental understanding, we looked into the different scenarios where shortest paths are sought, be it in unweighted or weighted graphs, & the existence of paths in these contexts. We then learned the algorithms that make finding these paths possible, highlighting Dijkstra's and Bellman-Ford's algorithms, each tailored for specific graph conditions.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Previous article
Topological Sorting in a Graph
Next article
Topological Sort of a Graph Using Departure Time of Vertex
Live masterclass