Dial’s algorithm:
Dial’s algorithm is a single-source shortest path algorithm. It is an optimization of Dijkstras when the graph has low edge weights. Similar to Dijkstras, it also doesn’t work on graphs with negative weights due to negative cycles.
E = edges, V = vertices, and W = max edge weight in the graph.
Dijkstra’s algorithm time complexity: O(E log(V))
Dial’s algorithm time complexity: O(E + WV)
The big difference between the two is how the nodes are stored when the search happens. Dijkstras commonly uses a heap to maintain its greed. While Dial’s algorithm just uses a bunch of queues, Dial recognized that using a heap on graphs with smaller edge weights was overkill. Dial’s algorithm will always work, but the memory used to maintain all queues for each possible value can get out of hand if it is too big.
Dial algorithm walkthrough:
First, make an array with exactly W * V queues. This guarantees that, given that graph, it has a queue for every possible value a path could have. Do a DFS from a selected node. Put all of the node’s children into the queue by the value of their path. For example, if the edge weight was 6, the algorithm would put that node into the paths with six value queues.
Then, the algorithm will go through the queue, starting with the smallest one. It will pop up at the front of the queue and add its children to the respective queues. If the node, when popped, has a path value of 4, all of its children will be put into the 4 + x queues. Just repeat this process until all nodes have been touched.
Dial’s only works on non-negative graphs, so when it wants to find the path with the smallest value, it doesn’t need to start from scratch. Since weights only add values, the path value will never be less than where it is currently.
In the end, the algorithm will leave with the same result as Dijkstras would have.
Dial Algorithim example:
In the slideshow blue nodes represent visited nodes and yellow nodes represent the current node being investigated.
I made the following slideshow: