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, 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 ('node' | | graph_nodes (I) .name | |', parent node:'| | node_dist_nt (I) .fpoint | 'distance:' | | node_dist_nt (I) .dvalue)

END LOOP

END cals_min_gdist

END