Информационный центр "Центральный Дом Знаний"

ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

cendomzn@yandex.ru

Наш опрос
Я учусь (закончил(-а) в школе техникуме институте академии университете Результаты \| Архив опросов Всего ответов: 2690

Онлайн всего: 1

Гостей: 1

Пользователей: 0

Форма входа

Алгоритм Данцига

Алгоритм Данцига, алгоритм для нахождения кратчайших путей ко всем вершинам планарного направленного графа. Назван в честь американского математика Джорджа Данцига. Алгоритм близок к алгоритму Флойда, отличается от него только другим порядком исполнения одних и тех же операций.

Шаг 1:

Пронумеровать вершины исходного графа целыми числами от 1 до N. Сформировать матрицу $D_{}^0$ (размерностью NxN), каждый элемент i, j которой $d_{ij}^0$ определяет длину кратчайшей дуги ведущей из вершины i в вершину j. В отсутствие такой дуги положить $d_{ij}^0 = \infty$ .

Шаг 2:

Здесь через $D_{}^m$ обозначается матрица размерностью mxm с элементами $d_{ij}^m, m = 1, 2,..., N$ . Последовательно определить элементы матрицы Dm из элементов матрицы Dm − 1 для mпринимающих значения 1,2,...N:

$d_{mj}^m = min_{i=1, 2, ... m-1}(d_{mi}^0 + d_{ij}^{m-1}) ( j = 1, 2, ..., m-1)$

$d_{im}^m = min_{j=1, 2, ... m-1}(d_{ij}^{m-1} + d_{jm}^{0} ) ( i = 1, 2, ..., m-1)$

$d_{ij}^m = min(d_{im}^{m} + d_{mj}^{m} , d_{ij}^{m-1} ) ( i, j = 1, 2, ..., m-1)$

Кроме того, для всех i и m положить $d_{ii}^m = 0$ .

Календарь

Архив записей
2010 Август 2010 Сентябрь 2010 Октябрь 2010 Ноябрь 2010 Декабрь 2011 Январь 2011 Февраль 2011 Март 2011 Апрель 2011 Май 2011 Июнь 2011 Июль 2011 Август 2011 Сентябрь 2011 Октябрь 2011 Ноябрь 2011 Декабрь 2012 Январь 2012 Февраль 2012 Ноябрь

Друзья сайта
Заказать курсовую работу! Выполнение любых чертежей Новый фриланс 24

Информационный центр "Центральный Дом Знаний"

Наш опрос

Форма входа

Алгоритм Данцига

Календарь

Архив записей

Друзья сайта