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.

Pseudo-code:

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:

1. 2d array where each cells value is its weight
2. source tuple (x, y)

Output:

1. distance matrix where each cell contains distance from source to vertex (i, j)

2. 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?