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 DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.
84+ registered