Die Darstellung des Graphen erfolgt in Form einer einfachen Tabelle mit den Spalten
ID, SOURCE, DESTINATION und DISTANCE.Als Beispiel dient der folgende Graph:
Die zugehörige Tabelle stellt sich dann wie folgt dar:
ID SOURCE DESTINATION DISTANCE
---------- ---------- ----------- --------
1 1 2 4
1 1 3 6
1 1 4 8
1 2 5 7
1 2 3 1
1 3 4 2
1 3 5 5
1 3 6 4
1 4 6 5
1 5 7 6
1 6 5 1
1 6 7 8
Auf dieser Grundlage sollen jetzt die kürzesten Wege ausgehend von Knoten 1 gefunden werden, wenngleich von jedem Knoten begonnen werden kann.Der Aufruf der PL/SQL-Table-Function geht so:
select * from table(dijkstra(1,1)) order by vertex;
VERTEX DISTANCE PREDECESSOR PATH
---------- -------- ----------- -----------------------
1 0 1
2 4 1 1 -> 2
3 5 2 1 -> 2 -> 3
4 7 3 1 -> 2 -> 3 -> 4
5 10 3 1 -> 2 -> 3 -> 5
6 9 3 1 -> 2 -> 3 -> 6
7 16 5 1 -> 2 -> 3 -> 5 -> 7
Die Spalte DISTANCE gibt die minimale Distanz zum jeweiligen Knoten an, die Spalte PREDECESSOR enthält den direkten Vorgänger und die Spalte PATH enthält die Knoten, welche auf dem kürzesten Weg zurückgelegt wurden.Nach dieser kurzen Demonstration der Funktionsweise hier der zugehörige Code:
-- Tabelle
drop table graph;
create table graph
(
id integer,
source integer,
destination integer,
distance number(38,2) not null
);
alter table graph
add constraint pk_graph
primary key (id, source, destination);
alter table graph
add constraint c_graph_source
check (source > 0);
alter table graph
add constraint c_graph_destination
check (destination > 0);
alter table graph
add constraint c_graph_distance
check (distance >= 0);
-- Daten
insert into graph(id,source,destination,distance)
values(1,1,2,4);
insert into graph(id,source,destination,distance)
values(1,1,3,6);
insert into graph(id,source,destination,distance)
values(1,1,4,8);
insert into graph(id,source,destination,distance)
values(1,2,5,7);
insert into graph(id,source,destination,distance)
values(1,2,3,1);
insert into graph(id,source,destination,distance)
values(1,3,4,2);
insert into graph(id,source,destination,distance)
values(1,3,5,5);
insert into graph(id,source,destination,distance)
values(1,3,6,4);
insert into graph(id,source,destination,distance)
values(1,4,6,5);
insert into graph(id,source,destination,distance)
values(1,5,7,6);
insert into graph(id,source,destination,distance)
values(1,6,5,1);
insert into graph(id,source,destination,distance)
values(1,6,7,8);
commit;
-- Type
drop type dijkstra_tab;
drop type dijkstra_t;
create type dijkstra_t as object
(
vertex integer,
distance binary_double,
predecessor integer,
path varchar2(4000)
);
/
create type dijkstra_tab as table of dijkstra_t;
/
-- Table function
create or replace
function dijkstra(p_graph_in in binary_integer, p_vertex_in in binary_integer) return dijkstra_tab pipelined
is
graph_not_found exception;
vertex_not_found exception;
type unchecked_tab is table of binary_integer index by binary_integer;
type predecessor_tab is table of binary_integer index by binary_integer;
type distance_tab is table of binary_double index by binary_integer;
cursor init_cur is
select source vertex
from graph
where id = p_graph_in
union
select destination vertex
from graph
where id = p_graph_in;
cursor distance_cur(pc_vertex_in in binary_integer) is
select destination, distance
from graph
where id = p_graph_in and source = pc_vertex_in;
i binary_integer;
v_dummy varchar(10);
v_unchecked unchecked_tab;
v_predecessor predecessor_tab;
v_distance distance_tab;
v_minimum binary_integer;
v_alternative binary_double;
v_path varchar2(4000);
begin
begin
select 'TRUE' into v_dummy
from dual
where exists
(
select *
from graph
where id = p_graph_in
);
exception
when no_data_found then
raise graph_not_found;
end;
begin
select 'TRUE' into v_dummy
from dual
where exists
(
select *
from graph
where id = p_graph_in and (source = p_vertex_in or destination = p_vertex_in)
);
exception
when no_data_found then
raise vertex_not_found;
end;
begin
for init_rec in init_cur loop
v_unchecked(init_rec.vertex) := null;
v_predecessor(init_rec.vertex) := null;
v_distance(init_rec.vertex) := binary_double_infinity;
end loop;
v_distance(p_vertex_in) := 0;
end;
begin
while (v_unchecked.count > 0) loop
v_minimum := null;
i := v_unchecked.first;
while (i is not null) loop
if (v_minimum is null) then
v_minimum := i;
else
if (v_distance(i) < v_distance(v_minimum)) then
v_minimum := i;
end if;
end if;
i := v_unchecked.next(i);
end loop;
v_unchecked.delete(v_minimum);
for distance_rec in distance_cur(v_minimum) loop
if (v_unchecked.exists(distance_rec.destination)) then
v_alternative := v_distance(v_minimum) + distance_rec.distance;
if (v_alternative < v_distance(distance_rec.destination)) then
v_distance(distance_rec.destination) := v_alternative;
v_predecessor(distance_rec.destination) := v_minimum;
end if;
end if;
end loop;
if (v_distance(v_minimum) = binary_double_infinity) then
v_path := '';
else
v_path := v_minimum;
end if;
i := v_predecessor(v_minimum);
while (i is not null) loop
v_path := i || ' -> ' || v_path;
i := v_predecessor(i);
end loop;
pipe row( dijkstra_t (
v_minimum,
v_distance(v_minimum),
v_predecessor(v_minimum),
v_path ) );
end loop;
end;
exception
when graph_not_found then
raise_application_error(-20010, 'DIJKSTRA: The graph was not found.');
when vertex_not_found then
raise_application_error(-20011, 'DIJKSTRA: The vertex to start the algorithm was not found.');
when others then
raise_application_error(-20012, 'DIJKSTRA: Unexpected error: ' || substr(1,200,SQLERRM));
end;
Keine Kommentare:
Kommentar veröffentlichen