В коде есть небольшая ошибка, из-за которой некоторые пути могут восстанавливаться некорректно, теряя связи. P[i][j] не должно быть равно k, так как не на каждой последующей итерации k - это ближайшая вершина к i при условии пути от вершины j, потому что в графе мы динамически заменяем изначально несуществующие пути на найденные. Решение заключается в том, чтобы так же динамически поддерживать список P: P[i][j] = P[i][k] В данном случае мы присваиваем P[i][j] вершину в действительности ближайщую к вершине i, если начинать наш путь от вершины j.
Здравствуйте. У вас 2 ошибки в коде. Про первую уже упомянули (P[i][j] = P[i][k] вместо P[i][j] = k). Вторая связана с функцией печати пути. У вас происходит проход с последней вершины в начальную, а надо с начальной в конечную. Исправленную реализацию прикрепил ниже (так же происходит зацикливание этой функции при отрицательных ребрах, этот случай никак не обработан ни у меня, ни у вас - можно по-хорошему обработать этот случай, возвращая пустой список): def get_path(history, start_vertex, end_vertex): path = [start_vertex] next_vertex = start_vertex while next_vertex != end_vertex: next_vertex = history[next_vertex][end_vertex] path.append(next_vertex) return path
Классный алгоритм, но в объяснении есть 2 недостатка: 1) Зачем приводить пример на цифрах, когда веса тоже цифры? Это очень затрудняет восприятие, лучше на каких-нибудь городах и т.д. 2) Лучше делать граф не в виде матрицы, а в виде словаря: все также удобнее для чтения + словари намного быстрее списков
Т.е. мы каждый раз при запросе ищем путь пробегая все варианты? А как насчет один раз пройти все варианты и записать данные в таблицу и потом просто выбирать нужные данные?
Тоже заметил, что программа не полностью корректна, несколько тестов показывают либо пропуски каких-либо точек в цепи, либо в разную сторону, строит разный маршрут...😕
В коде есть небольшая ошибка, из-за которой некоторые пути могут восстанавливаться некорректно, теряя связи.
P[i][j] не должно быть равно k, так как не на каждой последующей итерации k - это ближайшая вершина к i при условии пути от вершины j, потому что в графе мы динамически заменяем изначально несуществующие пути на найденные.
Решение заключается в том, чтобы так же динамически поддерживать список P:
P[i][j] = P[i][k]
В данном случае мы присваиваем P[i][j] вершину в действительности ближайщую к вершине i, если начинать наш путь от вершины j.
Спасибо, добрый человек!
Ваши ролики вместо игры в шахматы и зарядка для мозга.
Спасибо, Сергей!
Спасибо, Сергей.
В поддержку учебных видео.
Здравствуйте. У вас 2 ошибки в коде. Про первую уже упомянули (P[i][j] = P[i][k] вместо P[i][j] = k). Вторая связана с функцией печати пути. У вас происходит проход с последней вершины в начальную, а надо с начальной в конечную. Исправленную реализацию прикрепил ниже (так же происходит зацикливание этой функции при отрицательных ребрах, этот случай никак не обработан ни у меня, ни у вас - можно по-хорошему обработать этот случай, возвращая пустой список):
def get_path(history, start_vertex, end_vertex):
path = [start_vertex]
next_vertex = start_vertex
while next_vertex != end_vertex:
next_vertex = history[next_vertex][end_vertex]
path.append(next_vertex)
return path
Да вам дискретную математику нужно преподавать, очень хорошо обьясняете всё что угодно)
Не забывайте про Джанго :))) Хотя я и алгосы очень люблю )) Спасибо вам )
Джанго Освобожденный
Придём и туда
спасибо мужик
А можно сделать так, чтобы выводилось само значение кратчайшего пути?
Конечно, просуммируйте соответствующие веса матрицы связности и получите значение. Это хорошее практическое занятие.
@selfedu Как ты относишься к Хауди Хо?
никак, я его не смотрел )
Классный алгоритм, но в объяснении есть 2 недостатка:
1) Зачем приводить пример на цифрах, когда веса тоже цифры? Это очень затрудняет восприятие, лучше на каких-нибудь городах и т.д.
2) Лучше делать граф не в виде матрицы, а в виде словаря: все также удобнее для чтения + словари намного быстрее списков
Т.е. мы каждый раз при запросе ищем путь пробегая все варианты? А как насчет один раз пройти все варианты и записать данные в таблицу и потом просто выбирать нужные данные?
Хотелось бы разбор алгоритма Данцига
А что это за алгоритм?
Спасибо!
почему при start=2 и end=3 выдает [3, 1, 2], а если start=3 и end=2 выдает [2, 1, 0, 3] ?
Тоже заметил, что программа не полностью корректна, несколько тестов показывают либо пропуски каких-либо точек в цепи, либо в разную сторону, строит разный маршрут...😕
Флойд Майвезер
Ебать чел ты разрывную закинул, жоско рофлишь пиздец, ты аккуратнее, а то мало ли
@@override5028 птицы знают толк в пунктуации
@@Inteonmteca нет
@@Inteonmteca смотря какой вид птиц.
@@override5028 подводный вид червевидных птиц