Руководство по Ada (Ada 2022)

A.18.33 Пример использования контейнеров

Примеры

Следующий пример представляет собой реализацию алгоритма Дейкстры нахождения кратчайших путей в ориентированном графе с положительными весами рёбер. Граф представлен в виде отображения узлов на множества рёбер.

with Ada.Containers.Vectors;
with Ada.Containers.Doubly_Linked_Lists;
use Ada.Containers;
generic
type Node is range <>;
package Shortest_Paths is
type Distance is new Float range 0.0 .. Float'Last;
type Edge is record
To, From : Node;
Length : Distance;
end record;

package Node_Maps is new Vectors (Node, Node);
-- Алгоритм строит отображение, указывающее узел, используемый для достижения заданного
-- узла с наименьшим расстоянием.

package Adjacency_Lists is new Doubly_Linked_Lists (Edge);
use Adjacency_Lists;

package Graphs is new Vectors (Node, Adjacency_Lists.List);

package Paths is new Doubly_Linked_Lists (Node);

function Shortest_Path
(G : Graphs.Vector; Source : Node; Target : Node) return Paths.List
with Pre => G (Source) /= Adjacency_Lists.Empty_List;

end Shortest_Paths;

package body Shortest_Paths is
function Shortest_Path
(G : Graphs.Vector; Source : Node; Target : Node) return Paths.List
is
use Node_Maps, Paths, Graphs;
Reached : array (Node) of Boolean := (others => False);
-- Множество узлов, для которых кратчайшее расстояние до источника известно.

Reached_From : array (Node) of Node;
So_Far : array (Node) of Distance := (others => Distance'Last);
The_Path : Paths.List := Paths.Empty_List;
Nearest_Distance : Distance;
Next : Node;
begin
So_Far(Source) := 0.0;

while not Reached(Target) loop
Nearest_Distance := Distance'Last;

-- Найти ближайший ещё не достигнутый узел, перебирая все узлы.
-- Для более эффективного алгоритма используется очередь с приоритетами на этом шаге.

Next := Source;
for N in Node'First .. Node'Last loop
if not Reached(N)
and then So_Far(N) < Nearest_Distance then
Next := N;
Nearest_Distance := So_Far(N);
end if;
end loop;

if Nearest_Distance = Distance'Last then
-- Узел не найден, граф не связный
return Paths.Empty_List;

else
Reached(Next) := True;
end if;

-- Обновление минимального расстояния до вновь достижимых узлов.

for E of G (Next) loop
if not Reached(E.To) then
Nearest_Distance := E.Length + So_Far(Next);

if Nearest_Distance < So_Far(E.To) then
Reached_From(E.To) := Next;
So_Far(E.To) := Nearest_Distance;
end if;
end if;
end loop;
end loop;

-- Построение пути от целевого узла к исходному.

declare
N : Node := Target;
begin
Prepend (The_Path, N);
while N /= Source loop
N := Reached_From(N);
Prepend (The_Path, N);
end loop;
end;

return The_Path;
end;
end Shortest_Paths;

Обратите внимание, что эффект атрибута Constant_Indexing (на типе Vector) и атрибута Implicit_Dereference (на типе Reference_Type) состоит в том, что

G (Next)

является удобным сокращением для

G.Constant_Reference (Next).Element.all

Аналогично, эффект цикла:

for E of G (Next) loop
if not Reached(E.To) then
...
end if;
end loop;

эквивалентен:

что эквивалентно: