Почему не работает алгоритм поиска кратчайшего пути если в def dijkstra задать start что-то кроме нуля?
import math
import random
import copy
def graph_generator(n, mean_degree, max_weight):
if mean_degree < 2 * (n - 1) / n:
mean_degree = 2 * (n - 1) / n
if mean_degree > n - 1:
mean_degree = (n - 1)
num_of_edges = int(mean_degree * n / 2)
W = []
for i in range(n):
W.append(['-'] * n)
W[i][i] = 0
stack = []
for i in range(n):
stack.append(i)
random.shuffle(stack)
while stack:
first = stack.pop()
if stack:
second = random.choice(stack)
W[first][second] = W[second][first] = random.randint(1, max_weight)
edges_not_tree = num_of_edges - (n - 1)
for _ in range(edges_not_tree):
first = random.randint(0, n - 1)
second = random.randint(0, n - 1)
W[first][second] = W[second][first] = random.randint(1, max_weight)
return W
def save_to_file(weight_list, filename):
with open(filename, "w") as f:
for value in weight_list:
temp_str = ''
for i in value:
temp_str += str(i) + ' '
f.write(temp_str + '\n')
def to_inf(W):
for i in range(len(W)):
for j in range(len(W)):
if W[i][j] == '-':
W[i][j] = math.inf
return W
def arg_min(T, S):
amin = -1
m = math.inf # максимальное значение
for i, t in enumerate(T):
if t < m and i not in S:
m = t
amin = i
return amin
W2 = graph_generator(3, 1, 3)
W = [['-', 4, '-', '-', '-', '-', '-', '-', '-', '-', 5, 8],
['-', '-', 6, '-', '-', 8, '-', '-', '-', '-', '-', '-'],
['-', '-', '-', '-', 4, '-', '-', '-', '-', '-', '-', '-'],
['-', '-', '-', '-', 4, '-', '-', '-', '-', '-', '-', '-'],
['-', '-', '-', 5, '-', 3, '-', '-', '-', '-', '-', '-'],
['-', '-', '-', 3, '-', 6, '-', '-', '-', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-'],
['-', '-', '-', '-', 5, 3, '-', '-', '-', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', '-', 1, '-', 6, '-', '-'],
['-', '-', '-', '-', '-', 1, '-', '-', 8, '-', '-', '-'],
['-', '-', '-', '-', '-', '-', '-', '-', '-', 3, '-', 6],
['-', 3, 6, '-', '-', 4, '-', '-', 2, '-', '-', '-']]
to_inf(W)
def dijkstra(W, start, end):
D = copy.deepcopy(W)
Nodes = len(D)
Distance = [math.inf] * Nodes
starting_node = 0
visited = {starting_node}
Distance[starting_node] = 0
count = 0
optimal_links = [0] * Nodes
while starting_node != -1:
for j, dw in enumerate(D[starting_node]):
if j not in visited:
r = Distance[starting_node] + dw
if r < Distance[j]:
Distance[j] = r
optimal_links[j] = starting_node
starting_node = arg_min(Distance, visited)
if starting_node >= 0:
visited.add(starting_node)
Path = [end]
count += end
while end != start:
end = optimal_links[Path[-1]]
Path.append(end)
print("Путь из вершины ", start, ":", Path[::-1])
print("Длина кратчайшего пути: ", Distance[count])
dijkstra(W, 0, 5)
