Identifying Dijkstra's algorithm for shortest path
Dijkstra's algorithm can solve the shortest path problems for weighted graphs with non-negative weights. These are generally medium or hard problems where we need to find the shortest distance between any pair of nodes in a weighted graph. While we may be able to solve the problem using other shortest path algorithms like Bellman-Ford, they are usually less efficient for these specific problems.
If the problem statement or its solution follows the generic template below, it can be solved by applying Dijkstra's algorithm.
Given a weighted graph with non-negative weights, find the shortest path from a source to some or all other nodes.
Example
Let's consider the following problem as an example to better understand how to identify and solve shortest path problems using Dijkstra's algorithm.
Problem statement: Given an NxM grid filled with integer costs in each cell, such that stepping on a cell incurs the cost stored in it. Find the minimum cost path from the cell (0, 0) to the cell (N-1, M-1) if movement is allowed in the cardinal directions (up, down, left, right).
Liking the course? Check our discounted plans to continue learning.