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;