11 Replies Latest reply on Apr 1, 2008 5:16 AM by 551395

    find out the shortest route

    610373
      Hi
      I have two tables, nodes and links and the structure of the tables are
      sql> select * from node;
      node_id node_name node_type
      --------- ----------- ----------
      9001
      9002
      9003
      9004
      9005
      9006
      9007
      9008
      9009
      9010
      and so.........

      sql> select * from link;
      link_id start_node end_node distance
      -------- ----------- --------- ---------
      L1 9001 9002 50
      L2 9002 9005 350
      L3 9001 9003 80
      L4 9003 9008 150
      L5 9008 9005 253
      L6 9005 9004 174
      L7 9006 9009 186
      L8 9010 9009 40
      L9 9003 9010 1520
      L10 9002 9006 520
      L11 9004 9009 610
      and so on.......

      and the columns in the link table start and end nodes are referenced from the node_id of the node table and the condition is
      the links are not directed(i.e, the link should be existed from 9001-9002 and also 9002-9001)

      Now i want the possible route combinations from one node to another based on distances of the links(i.e, need to find the shortest path)

      for example

      i want the possible comb's from 9001 to 9010
      o/p should be like this

      result                         distance
      -----------------------------------------           ---------
      9001-9002-9005-9008-9003-9010      2323
      9001-9002-9006-9009-9010               610
      9001-9003-9008-9005-9002-9006-9009-9010     1579
      9001-9003-9008-9005-9004-9009-9010     1307     
      9001-9003-9010           1600
      9001-9002-9005-9004-9009-9010 1224

      Ant Help?
      Thank you
        • 1. Re: find out the shortest route
          610373
          If the data is directed then the following query is working fine
          giving the routes and the code is

          SQL> select ltrim(ys_connect_by_path(start_node,'-'),'-')||'-'|| end_node as path
          from link where end_node=9010
          start with start_node=9001
          connect by end_node = prior end_node and prior end_node <>9010

          then the o/p should be
          path
          -----------------------------------------------
          9001-9003-9010

          please do this if the link is not directed

          Thank you
          • 2. Re: find out the shortest route
            518523
            You will have to implement one of the shortest path algorithms.
            One such algorithm is Dijkstra's algorithm.

            http://en.wikipedia.org/wiki/Dijkstra's_algorithm
            • 3. Re: find out the shortest route
              610373
              Please any one can help me???

              Thank you
              • 4. Re: find out the shortest route
                RadhakrishnaSarma
                I could get only here so far.
                SQL> select * from t
                  2  /
                
                       LVL      NODE1      NODE2   DISTANCE
                ---------- ---------- ---------- ----------
                         1       9001       9002         50
                         2       9002       9005        350
                         3       9001       9003         80
                         4       9003       9008        150
                         5       9008       9005        253
                         6       9005       9004        174
                         7       9004       9009        610
                         8       9006       9009        186
                         9       9010       9009         40
                        10       9003       9010       1520
                        11       9002       9006        520
                        12       9010                     0
                
                12 rows selected.
                
                SQL> 
                SQL> select hr
                  2  from (select substr(sys_connect_by_path(node1, '->'), 3, 100) hr, 
                  3               distance,
                  4               rownum rn,
                  5               level col,
                  6               connect_by_root node1 rt
                  7        from (select lvl, node1, node2, distance 
                  8              from t
                  9              where node1 <> 9010
                 10              or (node1 = 9010
                 11                 and node2 is null)
                 12              union 
                 13              select lvl, node2, node1, distance 
                 14              from t
                 15              where node1 <> 9001
                 16              and node2 <> 9010 
                 17              )
                 18        connect by NOCYCLE prior node2 = node1
                 19        start with node1=9001
                 20       )
                 21  where substr(hr, -4, 4) = 9010
                 22  /
                
                HR
                ---------------------------------------------------------------------------------
                9001->9002->9005->9008->9003->9010
                9001->9002->9005->9004->9009->9010
                9001->9002->9006->9009->9004->9005->9008->9003->9010
                9001->9002->9006->9009->9010
                9001->9003->9008->9005->9002->9006->9009->9010
                9001->9003->9008->9005->9004->9009->9010
                9001->9003->9010
                
                7 rows selected.
                
                SQL> 
                I couldn't find a way to calculate the cumulative distance in the hierarchy. This may give you some idea.

                Cheers
                Sarma.
                • 5. Re: find out the shortest route
                  Frank Kulash
                  Hi,

                  The easiest way to do this involves a simple PL/SQL function that takes a string containing a numeric expression and returns the value of that expression. The solution then is simply a matter of evaluating SYS_CONNECT_BY_PATH (distance,'+'), making sure that there always is a numeric distance.
                  That is:
                  SELECT     &&src_node || path_txt                  AS result
                  ,     eval_number (SUBSTR (distance_txt, 2))     AS distance
                  FROM     (     -- Begin CONNECT BY query
                       SELECT     end_node
                       ,     SYS_CONNECT_BY_PATH (end_node, '-')          AS path_txt
                       ,     SYS_CONNECT_BY_PATH (NVL (distance, 0), '+')     AS distance_txt
                       FROM     (     -- Begin in-line view of links
                            SELECT     start_node
                            ,     end_node
                            ,     distance
                            FROM     link
                            WHERE     end_node     <> &&src_node
                            AND     start_node     <> &&dest_node
                            UNION
                            SELECT     end_node     AS start_node
                            ,     start_node     AS end_node
                            ,     distance
                            FROM     link
                            WHERE     start_node     <> &&src_node
                            AND     end_node     <> &&dest_node
                            )     -- End in-line view of links
                       START WITH          start_node     = &&src_node
                       CONNECT BY NOCYCLE     start_node     = PRIOR (end_node)
                       )     -- End CONNECT BY query
                  WHERE     end_node     = &&dest_node
                  ;
                  where eval_number is something like:
                  FUNCTION     eval_number
                  (     in_txt     IN     VARCHAR2
                  ,     err_val     IN     NUMBER     DEFAULT     NULL
                  )
                  RETURN     NUMBER
                  IS
                       result_txt     VARCHAR2 (100);
                       return_val     NUMBER;
                  BEGIN
                       EXECUTE IMMEDIATE     'SELECT '
                                 ||     in_txt
                                 ||     ' FROM dual'
                                 INTO     return_val;     -- result_txt
                       RETURN     return_val;
                  EXCEPTION
                       WHEN OTHERS
                       THEN -- Caller can supply value to flag errors
                            RETURN     err_val;
                  END     eval_number
                  ;
                  Below is a much messier solution that does not use PL/SQL. It involves querying the result set of the CONNECT BY query that includes the original ROWNUM. This result set may show (for example) a path that has LEVEL=3 on row 11. The total distance of that path is the sum of the distances from the last instance of each level up to and including 3 from the rows up to and including 11.
                  WITH cbq     AS
                       (     -- Begin CONNECT BY query
                       SELECT     LEVEL     AS lvl
                       ,     ROWNUM     AS rnum
                       ,     distance
                       ,     end_node
                       ,     SYS_CONNECT_BY_PATH (end_node, '-')          AS path_txt
                       ,     SYS_CONNECT_BY_PATH (NVL (distance, 0), '+')     AS distance_txt
                       FROM     (     -- Begin in-line view of links
                            SELECT     start_node
                            ,     end_node
                            ,     distance
                            FROM     link
                            WHERE     end_node     <> &&src_node
                            AND     start_node     <> &&dest_node
                            UNION
                            SELECT     end_node     AS start_node
                            ,     start_node     AS end_node
                            ,     distance
                            FROM     link
                            WHERE     start_node     <> &&src_node
                            AND     end_node     <> &&dest_node
                            )     -- End in-line view of links
                       START WITH          start_node     = &&src_node
                       CONNECT BY NOCYCLE     start_node     = PRIOR (end_node)
                       )     -- End CONNECT BY query
                  SELECT     &&src_node || path_txt
                       AS result
                  ,     (     -- Begin scalar sub-query to add up distances
                       SELECT     SUM (distance)
                       FROM     cbq     c2
                       WHERE     rnum     <= c1.rnum
                       AND     lvl     <= c1.lvl
                       AND     NOT EXISTS
                            (     -- Begin sub-query to look for later row at the same level
                            SELECT     NULL
                            FROM     cbq
                            WHERE     rnum     > c2.rnum
                            AND     rnum     <= c1.rnum
                            AND     lvl     = c2.lvl
                            )     -- End sub-query to look for later row at the same level
                       )     -- End scalar sub-query to add up distances
                       AS distance
                  FROM     cbq     c1
                  WHERE     end_node     = &&dest_node
                  ;
                  • 6. Re: find out the shortest route
                    RadhakrishnaSarma
                    This?

                    SQL> select * from t
                      2  /
                    
                           LVL      NODE1      NODE2   DISTANCE
                    ---------- ---------- ---------- ----------
                             1       9001       9002         50
                             2       9002       9005        350
                             3       9001       9003         80
                             4       9003       9008        150
                             5       9008       9005        253
                             6       9005       9004        174
                             7       9004       9009        610
                             8       9006       9009        186
                             9       9010       9009         40
                            10       9003       9010       1520
                            11       9002       9006        520
                            12       9010                     0
                    
                    12 rows selected.
                    
                    SQL> with tv as
                      2  (select ltrim(rtrim(hr)) hr,
                      3         rn,
                      4         nvl(distance, 0) distance,
                      5         col
                      6  from (select rownum rn,
                      7               prior distance distance,
                      8               level col,
                      9               substr(sys_connect_by_path(node1, '->'), 3, 100) hr
                     10        from (select lvl, node1, node2, distance
                     11              from t
                     12              where node1 <> 9010
                     13              or (node1 = 9010
                     14                 and node2 is null)
                     15              union
                     16              select lvl, node2, node1, distance
                     17              from t
                     18              where node1 <> 9001
                     19              and node2 <> 9010
                     20              )
                     21        connect by NOCYCLE node1 = prior node2
                     22        start with node1=9001
                     23       )
                     24  )
                     25  select hr, dist
                     26  from( select hr,
                     27               sum(distance) over (order by rn, col rows col - 1 preceding) dist,
                     28               rn,
                     29               col
                     30        from (select col,
                     31                     distance,
                     32                     hr,
                     33                     rn
                     34              from (select col,
                     35                           distance,
                     36                           rn,
                     37                           row_number( ) over (partition by col, rn
                     38                                               order by rown desc) rowval,
                     39                           hr
                     40                    from (select b.col col,
                     41                                 b.distance distance,
                     42                                 a.rn rn,
                     43                                 b.hr hr,
                     44                                 b.rn rown
                     45                          from tv b, (select col,
                     46                                             distance,
                     47                                             hr,
                     48                                             rn
                     49                                      from (select col,
                     50                                                   distance,
                     51                                                   rn,
                     52                                                   hr,
                     53                                                   lag(col) over (order by rn) prev
                     54                                            from tv
                     55                                           )
                     56                                      where col - prev <> 1
                     57                                      ) a
                     58                          where b.col < a.col
                     59                          and b.rn <= a.rn
                     60                         )
                     61                    )
                     62              where rowval = 1
                     63              union all
                     64              select col,
                     65                     distance,
                     66                     hr,
                     67                     rn
                     68              from tv)
                     69             )
                     70  where substr(hr, -4, 4) = 9010
                     71  order by rn, col
                     72  /
                    HR                                                                  DIST
                    -----------------------------------------------------------   ----------
                    9001->9002->9005->9008->9003->9010                           2323
                    9001->9002->9005->9004->9009->9010                           1224
                    9001->9002->9006->9009->9004->9005->9008->9003->9010                 3463
                    9001->9002->9006->9009->9010                    796
                    9001->9003->9008->9005->9002->9006->9009->9010                      1579
                    9001->9003->9008->9005->9004->9009->9010                      1307
                    9001->9003->9010                                     1600

                    7 rows selected.

                    SQL>
                    Cheers
                    Sarma.
                    • 7. Re: find out the shortest route
                      551395
                      The following code i thought is more simpler, though it requires a small function creation.

                      Function code is
                      --------------------------

                      create function calc_tot(x in varchar2) return number
                      as
                      str varchar2(4000):= 'Select '||trim(x)||' from dual';
                      temp number;

                      begin
                      execute immediate str into temp;
                      return temp;
                      exception
                      when others then
                      return -999999999;
                      end calc_tot;
                      /

                      Following sql will give you answer for any starting point to ending point with least distance being the top. I just used the data that Sarma used for ease of comparison.

                      ---------------------------------------------------------------------------------------------


                      with dt as (select lvl,node1,node2,distance from d
                      union
                      select lvl,node2,node1,distance from d
                      ),
                      dist as (SELECT sys_connect_by_path(node1, '->') || '->' || node2 path,
                      ltrim(sys_connect_by_path(distance, '+'),'+') dist_path
                      FROM dt
                      where node1 is not null and node2 is not null
                      CONNECT BY nocycle PRIOR node2 = node1
                      )
                      select path,calc_tot(dist_path) tot_dist from dist
                      where path like '->9001%9010'
                      order by tot_dist;

                      ->9001->9002->9006->9009->9010     796
                      ->9001->9003->9001->9002->9006->9009->9010     956
                      ->9001->9002->9005->9004->9009->9010     1224
                      ->9001->9003->9008->9005->9004->9009->9010     1307
                      ->9001->9003->9001->9002->9005->9004->9009->9010     1384
                      ->9001->9002->9001->9003->9008->9005->9004->9009->9010     1407
                      ->9001->9003->9008->9005->9002->9006->9009->9010     1579
                      ->9001->9003->9010     1600
                      ->9001->9002->9001->9003->9010     1700
                      ->9001->9002->9005->9008->9003->9010     2323
                      ->9001->9002->9006->9009->9004->9005->9008->9003->9010     3463
                      • 8. Re: find out the shortest route
                        RadhakrishnaSarma
                        Hi Maniappan,

                        The idea is not to use PL/SQL at all. By the way, your output has results in which the flight goes to starting point again.
                        ->9001->9003->9001->9002->9006->9009->9010 956
                        Cheers
                        Sarma.
                        • 9. Re: find out the shortest route
                          551395
                          Hi Radhakrishna,

                          Thanks for your feedback. Yeah, i too noticed the visiting the source back, since its just another alternate, can be ignored I thought becuase its always going to be having larger distance.

                          Thanks
                          Mani
                          • 10. Better SQL Solution
                            Frank Kulash
                            Hi,

                            I still think the best solution involves a little PL/SQL function that takes a string like '80+1520' and returns the value (1600).

                            For those who are interested in pure SQL solutions, here's a much cleaner one. It works by checking to see if the SYS_CONNECT_BY_PATH contains a substring that represents a particular arc in the link table (either order)>
                            WITH link2     AS
                                 (     -- Begin in-line view of links
                                 SELECT     start_node
                                 ,     end_node
                                 ,     distance
                                 FROM     link
                                 WHERE     end_node     <> &&src_node
                                 AND     start_node     <> &&dest_node
                                 UNION
                                 SELECT     end_node     AS start_node
                                 ,     start_node     AS end_node
                                 ,     distance
                                 FROM     link
                                 WHERE     start_node     <> &&src_node
                                 AND     end_node     <> &&dest_node
                                 )     -- End in-line view of links
                            SELECT     q1.result
                            ,     (     -- Begin scalar sub-query to compute SUM (distance)
                                 SELECT     SUM (distance)
                                 FROM     link2
                                 WHERE     '&&sep' || q1.result || '&&sep'     
                                      LIKE     '%&&sep' || start_node || '&&sep' || end_node || '&&sep%'
                                 )     -- End scalar sub-query to compute SUM (distance)
                                 AS distance
                            FROM     (     -- Begin hierarchical query q1
                                 SELECT     '&&src_node' || SYS_CONNECT_BY_PATH (end_node, '&&sep')     AS result
                                 ,     end_node
                                 FROM     link2
                                 START WITH          start_node     = &&src_node
                                 CONNECT BY NOCYCLE     start_node     = PRIOR end_node
                                 ) q1     -- End hierarchical query q1
                            WHERE     q1.end_node     = &&dest_node
                            ORDER BY     q1.result
                            ;
                            sep can be any separator string, including multi-character strings.
                            • 11. Re: Better SQL Solution
                              551395
                              Hi Frank,

                              Yeah you are right, this is relatively simpler looking sql solution.

                              Thanks
                              Mani