Dijkstra’s algorithm is great for finding the shortest distance from a start vertex to all other vertices in the graph. However, it is not the best when we are just looking for the shortest distance from a single start vertex to a single end vertex. Let’s think about this.

Dijkstra’s algorithm considers ALL neighboring vertices and simply pops the vertex with the shortest distance calculated so far from the queue. As a refresher, here’s the pseudocode for Dijkstra’s Algorithm:

create dictionary to map vertices to their distance from start vertex

assign start vertex a distance of 0 in min heap

assign every other vertex a distance of infinity in min heap

remove the vertex with the minimum distance from the min heap and set it to the current vertex

while min heap is not empty:
  for each current vertex:
    for each neighbor in neighbors:
    new distance = (distance to current vertex) + (edge weight of current vertex to neighbor)

    if new distance is less than its current distance:
      current distance = new distance

return distances

However, considering vertices that take us away from our goal might be a waste of time. For instance, take a look at the graph on the left.

What if we modeled all the train stations in North America using a graph and we were looking for the shortest train distance from New York to Los Angeles?

We shouldn’t consider train stations in Canada because it would be inefficient to look in that direction. However, as shown in the graph on the left, Dijkstra’s looks in all directions, and the algorithm will check all neighboring stations.

Luckily, there are modifications we can make to Dijkstra’s Algorithm. Let’s see how we can optimize it!