I have implemented
Dikstra's algorithm for my research on an Economic model, using Python.
In my research I am investigating two functions and the differences between them. Every functions takes as input two parameters:
Every cell of the matrix is defined as: $$M(a)(b)=|F(a,b)-Z(a,b)|$$
The purpose of this is to find the path of minimal difference between the equations that will be correct for every input
Online implementations of Dikstra’s algorithm were all using weighted edges whereas I have weighted vertecies.
function Dijkstra(Graph, source): create vertex set Q for each vertex v in Graph: dist(v) ← INFINITY prev(v) ← UNDEFINED add v to Q dist(source) ← 0 while Q is not empty: u ← vertex in Q with min dist(u) remove u from Q for each neighbor v of u: // only v that are still in Q alt ← dist(u) + length(u, v) if alt < dist(v): dist(v) ← alt prev(v) ← u return dist(), prev()
- 2d array where each cells value is its weight
- source tuple (x, y)
distance matrix where each cell contains distance from source to vertex (i, j)
prev matrix where each cell contains its parent. By tracebacking from (98,98) I can find the shortest path.
MAX_DISTANCE = 99999 RANGE_ARR = (x for x in range(1, 1001)) def dijkstra_get_min(Q, dist): min = MAX_DISTANCE + 1 u = None for vertex in Q: if dist(vertex(0), vertex(1)) <= min: min = dist(vertex(0), vertex(1)) u = vertex return u def dijkstra(graph, src=(0, 0)): dist = np.array((np.array((0 for x in RANGE_ARR), dtype=float) for y in RANGE_ARR)) prev = np.array((np.array(((0, 0) for x in RANGE_ARR), dtype='i,i') for y in RANGE_ARR)) Q = () for i in RANGE_ARR_0: for j in RANGE_ARR_0: dist(i, j) = MAX_DISTANCE prev(i, j) = (0, 0) Q.append((i, j)) dist(0)(0) = 0 while Q: u = dijkstra_get_min(Q, dist) Q.remove(u) moves = (x for x in ( (u(0), u(1) + 1), (u(0) + 1, u(1)), (u(0) + 1, u(1) + 1) ) if x in Q) for v in moves: alt = dist(u(0))(u(1)) + graph(v(0))(v(1)) if alt < dist(v(0))(v(1)): dist(v(0), v(1)) = alt prev(v(0), v(1)) = u return dist, prev
Any opinions about its correctness?