# Shortest paths from a single source (Dijkstra and Bellman-Ford)

I did not implement a priority queue in Dijkstra. I'm not sure if a trivial priority queue is the best choice, since, after each iteration, several elements change their value. Maybe it is better to just "bubble" modified elements to their new places.

Tests are implemented very roughly, but it is not the point here.

import random

class WeightedGraph:
# constructor randomley generates a graph,
# given the number of vertice, min and max number of vertice from each vertex
def __init__(self, number_vertice,
min_edges_per_vertice,
max_edges_per_vertice,
negative_weights_allowed = False):
assert number_vertice > 0
assert min_edges_per_vertice >= 0
assert max_edges_per_vertice < number_vertice
assert min_edges_per_vertice <= max_edges_per_vertice

self.edges_per_vertice = [[] for _ in xrange(number_vertice)]
for vertex_from in xrange(number_vertice):
number_of_edges = random.randint(min_edges_per_vertice, max_edges_per_vertice)
# to make sure there are no self loops,
# sample ends < counter and ends > counter separately
qty_edges_before = int(round(number_of_edges * vertex_from / number_vertice))
if qty_edges_before > number_of_edges:
qty_edges_before = number_of_edges
if qty_edges_before >= vertex_from:
qty_edges_before = vertex_from
if (number_of_edges-qty_edges_before) >= (number_vertice - vertex_from - 1):
qty_edges_before = number_of_edges + vertex_from - number_vertice + 1

vertice_to = []
if qty_edges_before > 0:
vertice_to += random.sample(xrange(vertex_from), qty_edges_before)
if qty_edges_before < number_of_edges:
vertice_to += random.sample(xrange(vertex_from+1, number_vertice), number_of_edges-qty_edges_before)

if negative_weights_allowed:
self.edges_per_vertice[vertex_from] = [(v, 2*random.random()-1) for v in vertice_to]
else:
self.edges_per_vertice[vertex_from] = [(v, random.random()) for v in vertice_to]
self.edges_per_vertice[vertex_from].sort(key = lambda x:x[0])

def Print(self):
vertex = -1
for epv in self.edges_per_vertice: # iterate over ends of the edge
vertex += 1
for other_vertice, weight in epv:
print "edge (", vertex, ", ", other_vertice, "), weight = ", weight

def BellmanFordPathToSrource(self, single_source):
assert single_source >= 0
assert single_source < len(self.edges_per_vertice)

# first element of a tuple is the distance, the second one is the ancestor
result = [(None, None) for _ in self.edges_per_vertice]
result[single_source] = (0, None) # distance to itself is 0
negative_loop_edge = None
for iteration in range(len(self.edges_per_vertice)): # iterate over lengths of paths, last loop for checking
for vertex_from in range(len(self.edges_per_vertice)): # iterate over beginning of the edge
for vertex_to, weight in self.edges_per_vertice[vertex_from]:
if result[vertex_to][0] == None: # we differentiate between 0 and None
continue # we cannot relax the edge that comes from unreachable vertice
new_distance = result[vertex_to][0] + weight
if (result[vertex_from][0] == None) or (result[vertex_from][0] > new_distance):
if iteration == len(self.edges_per_vertice) - 1:
negative_loop_edge = (vertex_from, vertex_to)
else:
result[vertex_from] = (new_distance, vertex_to)

for vertex in xrange(len(result)):
print "vertex ", vertex, ", distance ", result[vertex][0], ", ancestor ", result[vertex][1]
if negative_loop_edge:
print "negative_loop_edge: ", negative_loop_edge[0], ", ", negative_loop_edge[1]
return result, negative_loop_edge

def BellmanFordPathFromSource(self, single_source):
if not self.edges_per_vertice:
return
assert single_source >= 0
assert single_source < len(self.edges_per_vertice)

# first element of a tuple is the distance, the second one is the ancestor
result = [(None, None) for _ in self.edges_per_vertice]
result[single_source] = (0, None) # distance to itself is 0
for _ in self.edges_per_vertice: # iterate over lengths of paths, last loop for checking
relaxed_edge = None
for vertex_from in range(len(self.edges_per_vertice)): # iterate over the beginnings of the edge
relaxed_edge_this_vertex = self.__RelaxEdgesFromSource(result = result, vertex_from = vertex_from)
if not relaxed_edge:
relaxed_edge = relaxed_edge_this_vertex
if not relaxed_edge:
break #stop if during the iteration no edge was relaxed

negative_loop_edge = relaxed_edge
for vertex in xrange(len(result)):
print "vertex ", vertex, ", distance ", result[vertex][0], ", ancestor ", result[vertex][1]
if negative_loop_edge:
print "negative_loop_edge: ", negative_loop_edge[0], ", ", negative_loop_edge[1]
return result, negative_loop_edge

def __RelaxEdgesFromSource(self, result, vertex_from): #direction from source outwards
if result[vertex_from][0] == None: # we differentiate between 0 and None
return None # we cannot relax the edge that comes from unreachable vertice
relaxed_edge = None
for vertex_to, weight in self.edges_per_vertice[vertex_from]:
new_distance = result[vertex_from][0] + weight
if (result[vertex_to][0] == None) or (result[vertex_to][0] > new_distance):
result[vertex_to] = (new_distance, vertex_from)
relaxed_edge = (vertex_from, vertex_to) # this edge has been relaxed
return relaxed_edge # we return **any** relaxed edge, provided at least one edge was relaxed

def DijkstraFromSource(self, single_source):
assert single_source >= 0
assert single_source < len(self.edges_per_vertice)

visited_vertice = set()
queueing_vertice = {v for v in range(len(self.edges_per_vertice))}
result = [(None, None) for _ in range(len(self.edges_per_vertice))]#(distance, ancestor)
result[single_source] = (0, None) # distance to itself is 0

current_vertex = single_source
while current_vertex != None: #differentiate between 0 and None

#relax all edges from current_vertex
queueing_vertice.remove(current_vertex)
self.__RelaxEdgesFromSource(result = result, vertex_from = current_vertex)

# find next current vertex
current_vertex_candidate = None
min_distance_so_far = None
for vertex in queueing_vertice:
if (result[vertex][0] == None):
continue
if (min_distance_so_far != None):
if min_distance_so_far <= result[vertex][0]:
continue
current_vertex_candidate = vertex
min_distance_so_far = result[vertex][0]
current_vertex = current_vertex_candidate

for vertex in xrange(len(result)):
print "vertex ", vertex, ", distance ", result[vertex][0], ", ancestor ", result[vertex][1]
return result

if __name__ == '__main__':
random.seed(10000)
wg = WeightedGraph(5, 0, 0)
wg.Print()
wg.BellmanFordPathFromSource(single_source = 0); wg.DijkstraFromSource(single_source = 0);
wg = WeightedGraph(5, 4, 4)
wg.Print()
wg.BellmanFordPathFromSource(single_source = 0); wg.DijkstraFromSource(single_source = 0);
wg = WeightedGraph(5, 2, 3)
wg.Print()
wg.BellmanFordPathFromSource(single_source = 0); wg.DijkstraFromSource(single_source = 0);
wg = WeightedGraph(5, 1, 1, True)
wg.Print()
wg.BellmanFordPathFromSource(single_source = 0)


1. Follow the pep8 style guide
2. The self.edges_per_vertice initialization should be moved into its own function.
3. Many parts can be greatly simplified by optimized by using numpy with vectorized operations.
4. In Print (which shouldn't be called that, btw), you can use enumerate rather than keeping track of the vertex number manually.
5. You can do x <= y < z.
6. You should probably use single leading _, since your code doesn't benefit from name mangling.
7. You can reverse if (result[vertex_from][0] == None) or (result[vertex_from][0] > new_distance): and use a continue to reduce the nesting by one level.
8. You can use string replacement, for example print 'vertex {}, distance {}, ancestor {}'.format(vertex, *result[vertex]).
9. In BellmanFordPathToSrource, at the end define the string outside the loop with printstr = 'vertex {}, distance {}, ancestor {}' and then on each cycle of the loop replace it with print prinstr.format(vertex, *result[vertex]).
10. In BellmanFordPathToSrource, in the final loop you can use for vetex, vresult in enumerate(result) to avoid having to index into result.
11. In DijkstraFromSource, you can do set(range(x)) instead of using a set comprehension.
12. You can do [(x, y)]*z to make list of tuples. Do not do [[x, y]]*z, though.
13. You should use is None or is not None instead of == None or != None.
14. You don't need to wrap single if tests in ( ).
15. You should make a main function and put all the code in if __name__ == '__main__': in there. Then just call that function in if __name__ == '__main__':.