oracle shortest_path
CREATE OR REPLACE PACKAGE shortest_path_pkg
AS
TYPE node_dist_rt IS RECORD(fpoint INT, dvalue INT);
TYPE node_dist_tt IS TABLE OF node_dist_rt INDEX BY PLS_INTEGER;
TYPE graph_node_rt IS RECORD(NAME VARCHAR2(100), isvisited BOOLEAN);
TYPE graph_node_tt IS TABLE OF graph_node_rt INDEX BY PLS_INTEGER;
TYPE graph_dist_tt IS TABLE OF PLS_INTEGER INDEX BY PLS_INTEGER;
TYPE graph_dist_nt IS TABLE OF graph_dist_tt INDEX BY PLS_INTEGER;
PROCEDURE add_node(graph_nodes IN OUT graph_node_tt,NAME VARCHAR2);
FUNCTION get_minnode(graph_nodes IN graph_node_tt, graph_dists IN graph_dist_nt, dnode INT) RETURN PLS_INTEGER;
PROCEDURE add_node_dist(graph_dist_inst IN OUT graph_dist_nt, snode INT, enode INT, dvalue INT);
PROCEDURE cals_min_gdist(graph_nodes IN OUT graph_node_tt, graph_dist_inst IN graph_dist_nt, snode IN OUT INT);
PROCEDURE INIT_dist_inst(graph_dist IN OUT graph_dist_nt, nodes_cnt INT);
END;
CREATE OR REPLACE PACKAGE BODY shortest_path_pkg
AS
PROCEDURE add_node(graph_nodes IN OUT graph_node_tt, NAME VARCHAR2)
AS
tmp_node graph_node_rt;
BEGIN
tmp_node.name := NAME;
tmp_node.isvisited := FALSE;
graph_nodes(graph_nodes.count + 1) := tmp_node;
END add_node;
FUNCTION get_minnode(graph_nodes IN graph_node_tt, graph_dists IN graph_dist_nt, dnode INT) RETURN PLS_INTEGER
AS
dest_node PLS_INTEGER := -1;
minval PLS_INTEGER := 999999999;
BEGIN
FOR tlvl IN 1..graph_dists(dnode).count LOOP
IF NOT graph_nodes(tlvl).isvisited AND graph_dists(dnode)(tlvl) < minval THEN
minval := graph_dists(dnode)(tlvl);
dest_node := tlvl;
END IF;
END LOOP;
RETURN dest_node;
END get_minnode;
PROCEDURE add_node_dist(graph_dist_inst IN OUT graph_dist_nt, snode INT, enode INT, dvalue INT)
AS
BEGIN
graph_dist_inst(snode)(enode) := dvalue;
graph_dist_inst(enode)(snode) := dvalue;
END add_node_dist;
PROCEDURE INIT_dist_inst(graph_dist IN OUT graph_dist_nt, nodes_cnt INT)
AS
BEGIN
FOR i IN 1..nodes_cnt LOOP
FOR j IN 1..nodes_cnt LOOP
graph_dist(i)(j) := 999999999;
END LOOP;
END LOOP;
END init_dist_inst;
PROCEDURE cals_min_gdist(graph_nodes IN OUT graph_node_tt, graph_dist_inst IN graph_dist_nt, snode IN OUT INT)
AS
tmp_cnt INT := 0;
dest_node INT;
node_dist_nt node_dist_tt;
node_dist_rec node_dist_rt;
tmp_dist INT;
BEGIN
FOR i IN 1..graph_nodes.count LOOP
node_dist_rec.fpoint := snode;
node_dist_rec.dvalue := graph_dist_inst(snode)(i);
node_dist_nt(i) := node_dist_rec;
END LOOP;
WHILE (tmp_cnt < graph_nodes.count) LOOP
dest_node := get_minnode(graph_nodes,graph_dist_inst, snode);
IF(dest_node = -1) THEN
raise_application_error(-20001, 'there exists a gap');
END IF;
graph_nodes(dest_node).isvisited := TRUE;
tmp_dist := graph_dist_inst(snode)(dest_node);
FOR i IN 1..graph_nodes.count LOOP
IF(node_dist_nt(i).dvalue>(tmp_dist+graph_dist_inst(dest_node)(i))) THEN
node_dist_nt(i).dvalue := tmp_dist + graph_dist_inst(dest_node)(i);
node_dist_nt(i).fpoint := dest_node;
END IF;
END LOOP;
snode := dest_node;
tmp_cnt := tmp_cnt + 1;
END LOOP;
FOR i IN 1..node_dist_nt.count LOOP
dbms_output.put_line('节点'||graph_nodes(i).name||', 父节点: '||node_dist_nt(i).fpoint||' 距离：'||node_dist_nt(i).dvalue);
END LOOP;
END cals_min_gdist;
END;
