Ура, я живой, сегодня алгоритм дейкстры, а в следующий раз то, что хотел максим(честно, но только что-то одно, так что ты уж выбери)😎 Задача: Дан взвешенный ориентированный граф G(V, E), где V - множество вершин, а E - множество рёбер. Также дан вес каждого ребра w и стартовая вершина s. Необходимо найти самый лёгкий(ну, дешёвый) путь от стартовый вершины до всех остальных. Известное расстояние от старта до вершины z будем хранить в distance[z] (type(distance) == list()), причем изначально distance[z] = float('inf'). Алгоритм постепенно улучшает значение для каждого ребра(все лучше, чем +бесконечность). Как он работает? В общем, алгоритм находит вершину с минимальным известным весом и пытается сократить расстояние до всех её соседей(релаксация ребра, которая занимает константное количество действий). Таким образом, есть вероятность получить путь короче, чем нынешний. Говоря на языке алгоритмов, значение distance[i] меняется если есть ребро веса w[i][j] из вершины i в вершину j, если выполняется неравенство distance[i] + w[i][j] < distance[j]. Перепишем вышесказанное на лучшем языке программирования(Конечно, после КуМира) def deikstra(w, start): n = len(w) distance = [float("inf")] n distance[start] = 0 used = [False] n while True: i = None minimal_distance = float("inf") for v in range(n): if used[v]: continue if i is None or distance[v] < minimal_distance: i = v minimal_distance = distance[v] if i is None or distance[i] == float("inf"): break # нам некуда идти, хд used[i] = True # релаксация ребер:) (чилим) for j in range(n): if w[i][j] is None: continue distance[j] = min(distance[i] + w[i][j], distance[j]) return distance Здесь важно отметить, что мы уже не приходим в вершину, в которой были, поскольку предполагается, что путь к вершине стать короче не может. Вопрос: в каком случае алгоритм работать не будет? Спасибо за внимание!🤩 Максим, жду идеи! #графы 📺Channel 🤡Creator