Dijkstra's Algorithm modified to take negative edge weights 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] &lt; 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:

&gt;&gt;&gt;import dijkstra
&gt;&gt;&gt;G16 = {'a':[('b',3),('c',2)], 'b':[('c',-2)], 'c':[('d',1)], 'd':[]}
&gt;&gt;&gt;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.
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] &gt; 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] &lt; 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.