путь, то есть путь
путь, то есть путь с минимальным весом, между двумя вершинами графа. Эта задача разбивается на две подзадачи: сам путь и значение минимального веса . Обозначим ее через D[s,t]. Неизвестны алгоритмы, определяющие только D[s,t], все они определяют оценки от вершины s до всех остальных вершин графа. Определим D, как array[1..n] of integer. Предположим, что мы определили значения элементов массива D - решили вторую подзадачу. Определим сам кратчайший путь. Для s и t существует такая вершина v, что D[t]=D[v]+A[v,t]. Запомним v (например, в стеке) . Повторим процесс поиска вершины u, такой, что D[v]=D[u]+A[u,v], и так до тех пор, пока не дойдем до вершины с номером s. Последовательность t, v, u, ..., s дает кратчайший путь.
procedure Way(s,t:integer);
{D, A - глобальные структуры данных}
var v,u:integer;
Stack - локальная структура данных для хранения номеров вершин;
procedure Print;
{выводит содержимое Stack}
begin
...
end;
begin
<почистить Stack>;
<занести
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа