I am trying to write Dijkstra's Algorithm, however I am struggling on how to 'say' certain things in code. To visualize, here are the columns I want represented using arrays:
max_nodes
A B C Length Predecessor Visited/Unvisited
A 0 1 2 -1 U
B 1 0 1 -1 U
C 2 1 0 -1 U
So, there will be several arrays, as seen in my code below:
def dijkstra (graph, start, end)
network[max_nodes][max_nodes]
state [max_nodes][length]
state2 [max_nodes][predecessor]
state3 [max_nodes][visited]
initialNode = 0
for nodes in graph:
D[max_nodes][length] = -1
P[max_nodes][predecessor] = ""
V[max_nodes][visited] = false
for l in graph:
length = lengthFromSource[node] + graph[node][l]
if length < lengthFromSourceNode[w]:
state[l][length] = x
state2[l][predecessor]
state3[l][visited] = true
x +=1
The part in bold is where I am stuck on - I am trying to implement this section of the algorithm:
3. For current node, consider all its unvisited neighbors and calculate their tentative distance. For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance, overwrite the distance
4. When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal
I think I am on the right track, i'm just stuck on how to say 'start at a node, get the length from source to a node, if length is smaller, overwrite previous value, then move to next node