Почему не работает алгоритм

danilvar

Новичок
Пользователь
Май 5, 2021
2
0
1
Почему не работает алгоритм если начальную вершину start задать что-то кроме нуля?
Python:
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] == '-' or W[i][j] == 0:
                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 = [[0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 5, 8],
     [0, 0, 6, 0, 0, 8, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 5, 0, 3, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 5, 3, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 1, 0, 6, 0, 0],
     [0, 0, 0, 0, 0, 1, 0, 0, 8, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 6],
     [0, 3, 6, 0, 0, 4, 0, 0, 2, 0, 0, 0]]

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)
 

grushaas

Новичок
Пользователь
Фев 25, 2021
4
0
1
Если честно, то я не вижу даже вашу переменную 'start'.
 

danilvar

Новичок
Пользователь
Май 5, 2021
2
0
1
Если честно, то я не вижу даже вашу переменную 'start'.
Она находится ниже в def dijkstra
 

Форум IT Специалистов