Dijkstra's Algorithm modified to take negative edge weights

Question

In the following Python implementation I have used color coded vertices to implement the Dijkstra's Algorithm in order to take negative edge weights.

G16 = {'a':[('b',3),('c',2)], 'b':[('c',-2)], 'c':[('d',1)], 'd':[]} 
# the graph is a dictionary with they "key" as nodes and the "value" as a 
# list of tuples
# each of those tuples represent an edge from the key vertex to the first 
# element of the tuple
# the second element of the tuple is the weight of that edge. 
# so, 'a':[('b',3),('c',2)] means an edge from a to b with weight 3 
# and another edge from a to c with weight 2. 
class minq: #min_queue implementation to pop the vertex with the minimum distance
 def __init__(self,dist):
 self.elms = [] 
 def minq_len(self):
 return len(self.elms)
 def add(self,element):
 if element not in self.elms:
 self.elms.append(element)
 def min_pop(self,dist):
 min_cost = 99999999999 
 for v in self.elms: 
 min_cost = min(min_cost,dist[v])
 for key,cst in dist.items():
 if cst == min_cost:
 if key in self.elms:
 v = key
 self.elms.remove(v)
 return v
def modified_dijkstras(graph,n): 
 cost = {} 
 color = {} # color interpretation: w = white = unvisited, g = grey = to be processed, b = black = already processed
 for vertex in graph: 
 cost[vertex] = 9999999 #setting cost of each vertex to a large number
 color[vertex] = 'w' #setting color of each vertex as 'w'
 q = minq(cost)
 q.add(n) 
 cost[n] = 0 
 while q.minq_len() != 0:
 x=q.min_pop(cost)
 color[x] = 'g' 
 for j,cost_j in graph[x]:
 temp = cost[j]
 cost[j] = min(cost[j],cost[x] + cost_j)
 if cost[j] < temp and color[j] == 'b': #if the cost varries even when the vertex is marked 'b'
 color[j] = 'w' #color the node as 'w'
 if color[j] != 'g': 
 color[j] = 'g'
 q.add(j) #this can insert a vertex marked 'b' back into the queue. 
 color[x] = 'b' 
 return cost 

The following is what is returned when you run the code on the Python interpreter with the graph defined on top:

>>>import dijkstra
>>>G16 = {'a':[('b',3),('c',2)], 'b':[('c',-2)], 'c':[('d',1)], 'd':[]}
>>>dijkstra.modified_dijkstras(G16,'a')
{'a': 0, 'b': 3, 'c': 1, 'd': 2} 

Please let me know if this algorithm has a better runtime than Bellman Ford as I am not iterating through all the vertices repeatedly.

Please also report your analysis of the run time for this algorithm, if any.

• Janne Karila: A cycle in the graph seems to cause infinite looping. Bug?
• 301_Moved_Permanently: @JanneKarila What is the length of your cycle? It seems to be a normal behaviour to me if the cycle length is < 0: it will always be better to make an other round to get a shorter path...
• Janne Karila: @MathiasEttinger For example modified_dijkstras({'a':[('b',3)], 'b':[('a',1)]}, 'a')

Answer 1

I am afraid your implementation is in \$\Theta(EV)\$ in the worst case, and that is because in the outer while loop you iterate \$V\$ times and popping a node from your custom priority queue runs in \$n = V\$ steps, so we already have \$\Theta(V^2)\$. If your graph is really dense, the complexity will rise to \$\Theta(EV)\$.

In order to get it done efficiently without writing your (say, Fibonacci-) heap, you could import heapq

With it, you can come up with something like:

def sssp(graph, start_node):
 open = [(0, start_node)]
 closed = set()
 distance_map = {start_node: 0}
 while open:
 current_node = heapq.heappop(open)[1]
 if current_node in closed:
 continue
 closed.add(current_node)
 for child, arc_weight in graph[current_node]:
 if child in closed:
 continue
 tentative_distance = distance_map[current_node] + arc_weight
 if child not in distance_map.keys() or distance_map[child] > tentative_distance:
 distance_map[child] = tentative_distance
 heapq.heappush(open, (tentative_distance, child))
 return distance_map

The above runs in \$\Theta((E + V) \log V)\$. Also, the above version has a desirable property: it does not visit nodes that are disconnected from the source node. You might need to know which nodes are not reachable; to this end, you just make a lookup into distance_map: if a node is not there as a key, it is unreachable. This "pruning" may boost the performance if most graph nodes are not reachable from the source node.

About code

Note that PEP8 complains: you should have a single space after , and :. Also, in Python, it is customary to write the class names in CamelCase. Also, in line if color[j] < temp and color[j] == 'b' you have two spaces after the the if; PEP8 requires one space only.

Hope that helps.

Post scriptum

On G16 = {'a': [('b': -1)], 'b': [('a': -1)]} your implementation goes into an infinite loop; mine provides invalid results but does exit. If your graph has negative-weight cycles, I suggest you stick to Bellman-Ford; alright, its worst case running time is \$\Theta(EV)\,ドル but its constant factors are small, since it is just two nested loops.

• Mrinal Sourav: Thank you for all the effort. Apologies for the issues with the code; I am a python novice. However, what I wanted to know is if this works better than Bellman Ford or not, assuming that there are no negative cycles in the graphs provided to the code.
• coderodde: @MrinalSourav Not necessarily since the best case running time of Bellman-Ford is \$\Theta(E)\$. What you need to do is to implement Bellman-Ford and benchmark it against the Dijkstra's algorithm on much larger graphs.

Answer 2

Naming

Using short variable names may feel clever but is really counter-productive when reading the code from an external point of view as it may be hard to remember what variable correspond to what context. Some examples:

• minq -> MinimumDistanceQueue;
• self.elms -> self.elements;
• x -> current_node or simply node;
• j -> neighbour.

Containers

Checking existence of an element in a list is an \$\mathcal{O}(n)\$ operation. You should preferably use a set here. More, using a set enforce the unicity of its elements so you can get rid of the check.

The minq_len method should also be replaced by the __len__ method. The benefit is twofold:

• You can call len(q) to check the number of remaining elements;
• bool(q) return False when len(q) is 0, this can lead to simply write while q:.

Magic numbers

Instead of using arbitrarily large numbers (which may be lower than the largest cost of an arc), you can use None to denote uninitialized costs.

Nearest node

The min_pop method is clumsy as it is a two-step process. You can take advantage of python's min behaviour which can take any iterable and the fact that tuples compare their elements index by index (i.e. (1, 9999) is before (2, 0)) to:

1. Build an iterable of (distance, node) of each node in self.elements;
2. Take the minimum of this iterable in a single min call;
3. Extract the nearest node at index 1 of this minimum.

List-comprehensions or generator expressions can help along the way:

distances = [(dist[element], element) for element in self.elements]
nearest = min(distances)
nearest_node = nearest[1]

Which can be simplified into:

_, nearest_node = min((dist[element], element) for element in self.elements)

Colors

I don't really get why you color your nodes. The idea behind it seems to be that any "changed" node should be put back into the queue; then be it, put them directly back into the queue when you modify them rather than by looking at their (modified) color.

Proposed improvements

class MinimumDistanceQueue:
 def __init__(self):
 self.elements = set()
 def __len__(self):
 return len(self.elements)
 def add(self, node):
 self.elements.add(node)
 def pop(self, distances):
 _, nearest_neighbour = min(
 (distances[element], element)
 for element in self.elements)
 self.elements.remove(nearest_neighbour)
 return nearest_neighbour
def modified_dijkstras(graph, start):
 cost = dict.fromkeys(graph)
 cost[start] = 0
 q = MinimumDistanceQueue()
 q.add(start)
 while q:
 node = q.pop(cost)
 for neighbour, weight in graph[node]:
 distance = cost[node] + weight
 if cost[neighbour] is None or distance < cost[neighbour]:
 cost[neighbour] = distance
 q.add(neighbour)
 return cost
if __name__ == '__main__':
 G16 = {'a': [('b', 3), ('c', 2)], 'b': [('c', -2)], 'c': [('d', 1)], 'd': []}
 print(modified_dijkstras(G16, 'a'))

• Mrinal Sourav: Thank you for the improvement. Your code works just like mine and is much easier to read. Please let me know if there are some good references/books that can help me learn how to code in Python like that. Also, would you think, if we do not consider negative cycles, this algorithm would work better than Bellman-Ford?