Розв’язок задачі про найкоротший шлях використовуючи алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда – алгоритм пошуку найкоротшого шляху в зваженому орієтованому графі (на відміну від алгоритму Дейкстри допускає ребра з від’ємною вагою)

Читати далі

Побудова мінімального кістяка в неорієнтованому графі використовуючи алгоритм Борувки

Основна ідея алгоритму Борувки дещо подібна до алгоритму Крускала, тобто пошук мінімального кістяка також починається з розгляду n дерев, кожне з яких…

Читати далі

Приклад знаходження дерева мінімальної вартості для орієнтованого графа за алгоритмом Дейкстри

Розглянемо деякий орієнтований гряф, для якого потрібно знайти найкоротший маршрут від вершини 1 до всіх інших вершин. Для розв’язку задач

Читати далі

Знаходження найкоротшого шляху в орієнтованому графі за алгоритмом Дейкстри

Алгоритм Дейкстри – алгоритм знаходження найкоротших шляхів від однієї з вершин графа до всіх інших (алгоритм працює тільки для графів з додатною вагою ребер).

Читати далі