patternpythonMinor

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

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

bellmandijkstrashortestsourcepathssinglefordandfrom

Problem

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 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 = 0
assert single_source 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

Solution

Follow the pep8 style guide

The self.edges_per_vertice initialization should be moved into its own function.

Many parts can be greatly simplified by optimized by using numpy with vectorized operations.

In Print (which shouldn't be called that, btw), you can use enumerate rather than keeping track of the vertex number manually.

You can do x

You should probably use single leading _, since your code doesn't benefit from name mangling.

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.

You can use string replacement, for example print 'vertex {}, distance {}, ancestor {}'.format(vertex, *result[vertex]).

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]).

In BellmanFordPathToSrource, in the final loop you can use for vetex, vresult in enumerate(result) to avoid having to index into result.

In DijkstraFromSource, you can do set(range(x)) instead of using a set comprehension.

You can do [(x, y)]z to make list of tuples. Do not do [[x, y]]z, though.

You should use is None or is not None instead of == None or != None.

You don't need to wrap single if tests in ( ).

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__':`.

Context

StackExchange Code Review Q#96815, answer score: 3

Revisions (0)

No revisions yet.