I have been considering a modification to the Dijkstra algorithm that would negate the need for a relaxation step. Can I get people's opinions or a reason why this would not work? My implementation centers around a priority queue of edges rather than nodes. Here is a description of my implementation:
We have a directed Graph class with Node, and Edge subclasses.
Edges have a "weight", a "start" node, and an "end" node.
Nodes have a "dist" value (updated with the optimal distance to reach them),
as well as a "bestPath" value (updated with the optimal path to reach them),
and finally an "edges" list.
Dikstra (Node origin, Node goal):
Set settledNodes = {}
origin.dist = 0
settledNodes.add(origin)
Comparator<Edge, Edge> comparator = (edge1, edge2) ->
compareDoubles(edge1.weight + edge1.start.dist, edge2.weight + edge2.start.dist)
PriorityQueue<Edge> queue = new PriorityQueue<>(comparator)
queue.addAll(origin.edges)
while (!queue.Empty || settledNodes.size < Graph.size):
currEdge = queue.pop()
if (!settledNodes.contains(currEdge.end)):
currEdge.end.bestPath = currEdge
if (currEdge.end == goal):
return
currEdge.end.dist = currEdge.weight + currEdge.start.dist
queue.add(currEdge.end.edges)
settledNodes.add(currEdge.end)
Once the algorithm finishes, each node will have its "bestPath" field populated, containing the optimal edge to follow to reach that node. These edges can be back-traced in order to recreate the entire path.
I realize that my pseudocode is an unholy amalgamation of python and java - Sorry for that.
The approach here centers around iterating over a priority-queue of edges rather than a list/priority queue of nodes. What do people think? As far as I can tell it is still optimal, and it seems to me like this algorithm is better in some ways. For instance, it does not necessarily iterate over all the edges of a node it encounters (unlike Dijkstra). It ignores long edges by throwing them to the bottom of the priority queue, and it may find an optimal route without ever processing such nodes, thus saving a few (or many!) iterations.
I am pretty excited about this algorithm, but I can't find anything like this anywhere online, which makes me think there is some deep flaw that I am overlooking. I would love to hear feedback from people.