|
Читайте также: |
Пусть задан граф из n вершин и длина ребер.
1. Строим таблицу, где столбцы будут относиться к вершинам. Но на одном шаге таблица пуста.
2. Выбираем вершину, кот. будет основной на данном шаге из условия такой близости к исходной (вначале это вершина А).
3. Проставим расстояния от выделенной вершины до остальных (если вершины не соединены, то ставится «-», знак 
или Б).
4. Прекращаем заполнение столбца, у кот. была выделена вершина.
5. Среди оставшихся столбцов находим наименьшее значение. Вершина данного столбца будет выделена.
6. Повторяем шаг 2-5, но с условием: цифру, кот. мы записываем в расстояние от данной вершины, надо выбирать наименьшую из 2-х выше лежащей цифры или сумму цифр выбранной вершины + расстояние от выбранной вершины.
7. Построение таблицы завершается, когда выделена последняя вершина, расстояние которой не уменьшается.
Дата добавления: 2015-07-11; просмотров: 105 | Нарушение авторских прав