Shortest Paths and Dijkstra’s Algorithm | by Shuo Wang | Oct, 2020


Let’s focus on a bit of bit concerning the efficiency of the brand new algorithm.

Starting on the first node, we set its distance to zero and add it to the min heap with its present distance as the type key. Then, so long as the min heap just isn’t empty, regularly pop off the node with the minimal key, loop via all of its related nodes and replace their shortest distance and push them onto the min heap if the brand new distance is a shorter distance.

One vital factor to concentrate to is the next strains within the loop:

# examine if the nodes has been up to date
if cur[0] != cur[1].distance:

This checks if the important thing of the thing on the heap is similar as the present shortest distance of the node. Consider the next scenario:

nodes = [1, 2, 3, 4]
edges = [(1, 2, 1), (1, 3, 4), (2, 4, 10), (3, 4, 2)]

If I’ve a graph of Four nodes: 1, 2, 3, 4

node1 — node2, distance 1

node1 — node3, distance 4

node2 — node4, distance 10

node3 — node4, distance 2

Start: push begin node onto heap with distance 0

[(0, node0_dist0)]

Iteration 1: During the primary iteration, the min heap incorporates node1 with key 0, it’s then popped off and its neighbors added to the heap.

[(1, node2_dist1), (4, node3_dist4)]

Iteration 2: node2 is popped off and its neighbors added.

[(4, node3_dist4), (11, node4_dist11)]

Iteration 3: node3 is popped off and its neighbors added.

But wait! node3’s neighbor, node4, is already on the queue, the one distinction is that its shortest distance is up to date to six now:

[(6, node4_dist6), (11, node4_dist6)]

You see, there are literally two entries for node4 within the heap, one with key 6 and one with key 11, just one entry has the important thing equaling to the present node4’s distance worth.

In the following iteration, the entry with key 6 is popped off because it’s the minimal key, and its neighbors processed, however since its neighbors all have shortest distance already, they gained’t make it onto the queue. and just one entry is left:

[(11, node4_dist6)]

In this case, you’ll clearly need to ignore it, since node4 is processed already, and the way in which you possibly can inform is that the important thing and the node4’s shortest distance doesn’t equal one another.


Source hyperlink

Write a comment