Я пытаюсь написать Алгоритм Дейкстры, однако я пытаюсь понять, как «сказать» определенные вещи в коде.Для наглядности вот столбцы, которые я хочу представить с помощью массивов:
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
Итак, будет несколько массивов, как видно из моего кода ниже:
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
Часть, выделенная жирным шрифтомвот где я застрял - я пытаюсь реализовать этот раздел алгоритма:
3.Для текущего узла рассмотрите все его не посещенные соседи и вычислите их предварительное расстояние.Например, если текущий узел (A) имеет расстояние 6, а ребро, соединяющее его с другим узлом (B), равно 2, расстояние от B до A будет 6 + 2 = 8.Если это расстояние меньше ранее записанного расстояния, перезапишите расстояние
4. Когда мы закончим с учетом всех соседей текущего узла, отметьте его как посещенный.Посещенный узел больше не будет проверяться;его записанное расстояние является окончательным и минимальным
Я думаю, что я на правильном пути, я просто застрял в том, как сказать «начать с узла, получить длину от источника до узла,если длина меньше, перезапишите предыдущее значение, затем перейдите к следующему узлу