Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Скриптовые языки программирования > Python
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 05.05.2021, 15:16   #1
danilvar
Новичок
Джуниор
 
Регистрация: 05.05.2021
Сообщений: 1
По умолчанию Почему не работает алгоритм

Почему не работает алгоритм поиска кратчайшего пути если в def dijkstra задать start что-то кроме нуля?
Код:
import random
import pprint
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')


W = graph_generator(6, 1, 9)
pprint.pprint(W)


def dijkstra(D, start, end):
    W = copy.deepcopy(D)
    n = len(W)
    count = 1
    for i in range(n):
        path[i] = W[start][i]

    visited[n] = {0}
    while count < n:
        minVal = 100
        for i in range(n):
            if visited == 0 and path[i] < minVal:
                minVal = path[i]
                minNode = i
        visited[minNode] = 1
        for i in range(n):
            if visited[i] == 0:
                path[i] = min(path[i], minVal + W[minNode][i])
        ++count
    path[start] = 0
    for i in range(n):
        print(path[i])


S = dijkstra(D, 1, 2)
danilvar вне форума Ответить с цитированием
Старый 06.05.2021, 12:46   #2
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Код:
S = dijkstra(D, 1, 2)
А что есть в этом вызове D?
Код:
def dijkstra(D, start, end):
    W = copy.deepcopy(D)
...
И тогда что тут копируется?
Ну и так далее ...
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Не работает gets вообще, ни один код не работает с gets, почему? Мaкс Общие вопросы C/C++ 4 26.07.2018 11:49
почему прсер работает на одних сайтах и не работает на других PHP_DELETANT PHP 4 12.02.2016 13:45
Здравствуйте ! в чем проблема,почему почему время исполнения операций не работает ? ion leahu Помощь студентам 6 23.11.2014 19:36
Почему программа на С++ не работает с локальным описанием массива, но работает с глобальным? >>STINGER<< Помощь студентам 4 08.03.2011 09:56
почему интеренет на Xp не работает, а на семерке работает Lenura Windows 18 04.10.2010 12:04