Предыдущая страница реферата | 7  8  9  10  11  12  13  14  15  16  17 | Следующая страница реферата

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

Можно предложить много процедур решения этой задачи, например, физическое моделирование такого рода: на плоской доске рисуется карта местности, в города и в развилки вбиваются гвозди, на каждый гвоздь надевается кольцо, дороги укладываются веревками, которые привязываются к соответствующим кольцам. Чтобы найти кратчайшее расстояние между кольцом 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;

Visited[i]:=True; C[i]:=0;

2 (общий шаг). Найти минимум среди неотмеченных (т.е. тех к, для которых Visitid[k]=False); пусть минимум достигается на индексе j, т.е. Len[j]£Len[k];

Затем выполнять следующие операции:

Visited[i]:=True;

если Len[k]>Len[j]+Matrix[j, k], то (Len[k]:=Len[j]+Matrix[j, k]; C[k]:=j)

z:=C[k];

Выдать z

z:=C[z]. Если z =0, то конец,

иначе перейти к 3.2.

Теорема. Алгоритм Дейкстры – корректен.

Uses Crt;

Const MaxSize=10;

Infinity=1000;

Var Mattr: array [1..MaxSize, 1..MaxSize] of integer;

Visited: array [1..MaxSize] of boolean;

Len,Path: array [1..MaxSize] of integer;

n, Start, Finish, k, i: integer;

Procedure Init;

Var f: text;

Рекомендуем скачать другие рефераты по теме: экологические рефераты, конспект 2 класс.





Предыдущая страница реферата | 7  8  9  10  11  12  13  14  15  16  17 | Следующая страница реферата