Алгоритм Дейкстры — страница 7

  • Просмотров 5047
  • Скачиваний 94
  • Размер файла 307
    Кб

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Седьмая итерация Шаг 2. ; ; Шаг 3. соответствует x10. Шаг 4. x10 получает постоянную пометку l(x10)=18+, p=x10. Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Восьмая итерация Шаг 2. ; Шаг 3. соответствует x5. Шаг 4. x5 получает постоянную пометку l(x5)=19+, p=x5. Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Девятая итерация Шаг 2. ;

Шаг 3. x9 получает постоянную пометку l(x9)=21+. Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа Алгоритм работает так: Шаг 1. . Первая итерация Шаг 2. ; ; Шаг 3. соответствует x7. Шаг 4. x7 получает постоянную пометку l(x7)=6+, p=x7. Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Вторая итерация Шаг 2. ; Шаг 3. соответствует x2. Шаг 4. x2 получает постоянную пометку l(x2)=7+, p=x2. Шаг 5. Не все вершины имеют постоянные

пометки, поэтому переходим к шагу 2. Третья итерация Шаг 2. ; Шаг 3. соответствует x4. Шаг 4. x4 получает постоянную пометку l(x4)=8+, p=x4. Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Четвертая итерация Шаг 2. ; ; ; Шаг 3. соответствует x5. Шаг 4. x5 получает постоянную пометку l(x5)=16+, p=x5. Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Пятая итерация Шаг 2. ; ; Шаг 3. соответствует x8. Шаг 4. x8 получает

постоянную пометку l(x8)=16+, p=x8. Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Шестая итерация Шаг 2. ; Шаг 3. соответствует x3. Шаг 4. x3 получает постоянную пометку l(x3)=18+, p=x3. Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Седьмая итерация Шаг 2. ; Шаг 3. x6 получает постоянную пометку l(x6)=20+. 3. Алгоритмизация задачи Вводим количество вершин неориентированного графа. Если количество

вершин больше 5, то переходим к пункту 3; иначе переходим к пункту 4. Генератором случайных чисел произвольно задаются связи между вершинами в матрице смежностей, переходим к пункту 5. Вводим связи между вершинами, исходя из следующего условия: если не существует пути длиной в одно ребро из одной вершины в другую, то ставим «100», если существует путь между двумя вершинами, то ставим произвольное положительное ненулевое значение

веса дуги. Все введенные данные заносятся в матрицу смежностей. Вводим номера вершин, путь между которыми нужно найти. Задаем начальные значения длин путей равных 100 (в программе это обозначает бесконечность), а пометки всех вершин обнуляем. Для начальной вершины в матрицу, хранящую пути (предшествующие вершины), заносим значение нуль, поскольку нет вершин предшествующих началу, значению пути присваиваем значение нуля, пометку