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:
F(a,b)
and Z(a,b)
.
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 a
Online implementations of Dikstra’s algorithm were all using weighted edges whereas I have weighted vertecies.
Pseudocode:
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()
Input:
 2d array where each cells value is its weight
 source tuple (x, y)
Output:

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.
Implementation:
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?