Реферат: Aлгоритмы на графах

Writeln('Length= ', len);

Readkey

End.

Для такого входного файла

8

0 23 12 1000 1000 1000 1000 1000

23 0 25 1000 22 1000 1000 35

12 25 0 18 1000 1000 1000 1000

1000 1000 18 0 1000 20 1000 1000

1000 22 1000 1000 0 23 14 1000

1000 1000 1000 20 23 0 24 1000

1000 1000 1000 1000 14 24 0 16

1000 35 1000 1000 1000 1000 16 0

программа напечатает:

1–3

5–7

7–8

3–4

4–6

2–5

1–2

Length= 125.

Алгоритм Дейкстры.

Дана дорожная сеть, где города и развилки будут вершинами, а дороги – ребрами. Требуется найти кратчайший путь между двумя вершинами.

Можно предложить много процедур решения этой задачи, например, физическое моделирование такого рода: на плоской доске рисуется карта местности, в города и в развилки вбиваются гвозди, на каждый гвоздь надевается кольцо, дороги укладываются веревками, которые привязываются к соответствующим кольцам. Чтобы найти кратчайшее расстояние между кольцом i и кольцом k, нужно взять i в одну руку, взять k в другую и растянуть. Те веревки, которые натянутся и не дадут разводить шире, и образуют кратчайший путь между i и k. Однако, математическая процедура, которая промоделирует эту физическую, выглядит очень сложно. Известны алгоритмы попроще, например, предложенный Дейкстрой еще в 1959 г. Этот алгоритм решает более общую задачу:

В ориентированной, неориентированной или смешанной сети найти кратчайший путь из заданной вершины во все остальные вершины.

Алгоритм использует три массива из n чисел каждый. Первый массив Visited содержит метки с двумя значениями: False (вершина еще не рассмотрена) и True (вершина уже рассмотрена); второй массив Len содержит расстояния от – текущие кратчайшие расстояния от начальной до соответствующей вершины; третий массив C содержит номера вершин – k-ый элемент C есть номер предпоследней вершины на текущем кратчайшем пути из начальной вершины в k-ю. Используется также Matrix – матрица расстояний.

Опишем алгоритм Дейкстры:

1 (инициализация). В цикле от 1 до n заполнить значением False массив Visited; заполнить числом i массив C (i – номер стартовой вершины); перенести i-ю строку матрицы Matrix в массив Len;