Алгоритм Данцига: відмінності між версіями
Перейти до навігації
Перейти до пошуку
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м →Джерело: категоризація |
Luver (обговорення | внесок) вікіфікація |
||
Рядок 1: | Рядок 1: | ||
'''Алгоритм Данцига''' |
'''Алгоритм Данцига''' — алгоритм для знаходження найкоротших шляхів до всіх вершин [[планарний спрямований граф|планарного спрямованого графа]]. Названий на честь американського математика [[Джордж Данцига|Джорджа Данцига]]. Алгоритм близький до [[ Алгоритм Флойда-Воршала|алгоритму Флойда]], відрізняється від нього лише іншим порядком виконання одних і тих же операцій. |
||
== Алгоритм == |
== Алгоритм == |
||
Рядок 19: | Рядок 19: | ||
== Дивіться також == |
== Дивіться також == |
||
[[ Алгоритм Флойда-Воршала|Алгоритм Флойда |
[[ Алгоритм Флойда-Воршала|Алгоритм Флойда — Воршала]] |
||
== Джерело == |
== Джерело == |
||
Російська Вікіпедія |
Російська Вікіпедія — [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B0%D0%BD%D1%86%D0%B8%D0%B3%D0%B0 Алгоритм Данцига] |
||
[[Категорія:Алгоритми]] |
[[Категорія:Алгоритми]] |
Версія за 18:59, 27 січня 2012
Алгоритм Данцига — алгоритм для знаходження найкоротших шляхів до всіх вершин планарного спрямованого графа. Названий на честь американського математика Джорджа Данцига. Алгоритм близький до алгоритму Флойда, відрізняється від нього лише іншим порядком виконання одних і тих же операцій.
Алгоритм
Крок 1
Пронумерувати вершини вихідного графа цілими числами від до . Сформувати матрицю (розмірністю ), кожен елемент , якої визначає довжину найкоротшої дуги яка веде з вершини у вершину . В разі відсутності такої дуги покласти .
Крок 2
Тут через позначається матриця розмірністю з елементами . Послідовно визначити елементи матриці з елементів матриці для що приймають значення :
Крім того, для всіх i і m покласти .
Дивіться також
Джерело
Російська Вікіпедія — Алгоритм Данцига