Find all distinct paths in a directed graph and compute minimal cost

graph, oracle, path, sql

Solution

Through a little abuse of `SYS_CONNECT_BY_PATH` and a function to use regular expressions to extract numbers from a list you can do:

SQL Fiddle

Oracle 11g R2 Schema Setup:

CREATE TABLE graph
( company VARCHAR2(10)
, "from" VARCHAR2(15)
, "to" VARCHAR2(15)
, cost NUMBER(18,2))
/

BEGIN
  INSERT INTO graph VALUES('Lufthansa', 'San Francisco', 'Denver', 1000);
  INSERT INTO graph VALUES('Lufthansa', 'San Francisco', 'Dallas', 10000);
  INSERT INTO graph VALUES('Lufthansa', 'Denver', 'Dallas', 500);
  INSERT INTO graph VALUES('Lufthansa', 'Denver', 'Chicago', 2000);
  INSERT INTO graph VALUES('Lufthansa', 'Dallas', 'Chicago', 600);
  INSERT INTO graph VALUES('Lufthansa', 'Dallas', 'New York', 2000);
  INSERT INTO graph VALUES('Lufthansa', 'Chicago', 'New York', 3000);
  INSERT INTO graph VALUES('Lufthansa', 'Chicago', 'Denver', 2000);
END;
/

CREATE TABLE paths
( "from" VARCHAR2(15)
, "to" VARCHAR2(15)
, minimal_cost NUMBER)
/

CREATE OR REPLACE FUNCTION sum_costs (
  vals VARCHAR2
) RETURN NUMBER
AS
  num_vals SIMPLE_INTEGER := REGEXP_COUNT( vals, '\d+' );
  total graph.cost%TYPE := 0;
BEGIN
  FOR i IN 1 .. num_vals LOOP
    total := total + TO_NUMBER( REGEXP_SUBSTR( vals, '\d+', 1, i ) );
  END LOOP;
  RETURN total;
END;
/

Query 1:

WITH costs AS (
  SELECT     CONNECT_BY_ROOT "from" AS "from",
             "to",
             sum_costs( SYS_CONNECT_BY_PATH ( cost, ',' ) ) AS total_cost
  FROM       graph
  WHERE      CONNECT_BY_ROOT "from" <> "to"
  CONNECT BY NOCYCLE PRIOR "to" = "from"
)
SELECT "from",
       "to",
       MIN( total_cost )
FROM   costs
GROUP BY "from", "to"

Results:

|          FROM |       TO | MIN(TOTAL_COST) |
|---------------|----------|-----------------|
|        Dallas |  Chicago |             600 |
|       Chicago | New York |            3000 |
|       Chicago |   Denver |            2000 |
| San Francisco |   Denver |            1000 |
|        Dallas | New York |            2000 |
|        Denver |  Chicago |            1100 |
| San Francisco | New York |            3500 |
|        Denver |   Dallas |             500 |
|        Dallas |   Denver |            2600 |
|        Denver | New York |            2500 |
| San Francisco |   Dallas |            1500 |
| San Francisco |  Chicago |            2100 |
|       Chicago |   Dallas |            2500 |

And this gets an optimal route for each pair of destinations as well:

Query 2:

WITH costs AS (
  SELECT     CONNECT_BY_ROOT "from" AS "from",
             "to",
             SUBSTR( SYS_CONNECT_BY_PATH ( "from", ',' ), 2 ) || ',' || "to" AS route,
             sum_costs( SYS_CONNECT_BY_PATH ( cost, ',' ) ) AS total_cost
  FROM       graph
  WHERE      CONNECT_BY_ROOT "from" <> "to"
  CONNECT BY NOCYCLE PRIOR "to" = "from"
)
SELECT
       "from",
       "to",
       MIN( route ) KEEP ( DENSE_RANK FIRST ORDER BY total_cost ) AS optimal_route,
       MIN( total_cost ) AS minimum_cost
FROM   costs
GROUP BY "from", "to"

Results:

|          FROM |       TO |                        OPTIMAL_ROUTE | MINIMUM_COST |
|---------------|----------|--------------------------------------|--------------|
|        Dallas |   Denver |                Dallas,Chicago,Denver |         2600 |
|        Dallas |  Chicago |                       Dallas,Chicago |          600 |
|        Dallas | New York |                      Dallas,New York |         2000 |
|        Denver |   Dallas |                        Denver,Dallas |          500 |
|        Denver |  Chicago |                Denver,Dallas,Chicago |         1100 |
|        Denver | New York |               Denver,Dallas,New York |         2500 |
|       Chicago |   Dallas |                Chicago,Denver,Dallas |         2500 |
|       Chicago |   Denver |                       Chicago,Denver |         2000 |
|       Chicago | New York |                     Chicago,New York |         3000 |
| San Francisco |   Dallas |          San Francisco,Denver,Dallas |         1500 |
| San Francisco |   Denver |                 San Francisco,Denver |         1000 |
| San Francisco |  Chicago |  San Francisco,Denver,Dallas,Chicago |         2100 |
| San Francisco | New York | San Francisco,Denver,Dallas,New York |         3500 |

And a pure SQL solution:

Query 3:

WITH Routes AS (
  SELECT     CONNECT_BY_ROOT "from" AS "from",
             "to",
             SUBSTR( SYS_CONNECT_BY_PATH ( "from", ',' ), 2 ) || ',' || "to" AS route,
             cost
  FROM       graph
  WHERE      CONNECT_BY_ROOT "from" <> "to"
  CONNECT BY NOCYCLE PRIOR "to" = "from"
),
costs AS (
  SELECT r."from",
         r."to",
         r.route,
         SUM( s.cost ) AS total_cost
  FROM   Routes r
         INNER JOIN
         Routes s
         ON (    r."from" = s."from"
             AND LENGTH( r.route ) >= LENGTH( s.route )
             AND SUBSTR( r.route, 1, LENGTH( s.route ) ) = s.route )
  GROUP BY r."from", r."to", r.route
)
SELECT "from",
       "to",
       MIN( route ) KEEP ( DENSE_RANK FIRST ORDER BY total_cost ) AS optimal_route,
       MIN( total_cost )
FROM   costs
GROUP BY "from", "to"

Results:

|          FROM |       TO |                        OPTIMAL_ROUTE | MIN(TOTAL_COST) |
|---------------|----------|--------------------------------------|-----------------|
|        Dallas |   Denver |                Dallas,Chicago,Denver |            2600 |
|        Dallas |  Chicago |                       Dallas,Chicago |             600 |
|        Dallas | New York |                      Dallas,New York |            2000 |
|        Denver |   Dallas |                        Denver,Dallas |             500 |
|        Denver |  Chicago |                Denver,Dallas,Chicago |            1100 |
|        Denver | New York |               Denver,Dallas,New York |            2500 |
|       Chicago |   Dallas |                Chicago,Denver,Dallas |            2500 |
|       Chicago |   Denver |                       Chicago,Denver |            2000 |
|       Chicago | New York |                     Chicago,New York |            3000 |
| San Francisco |   Dallas |          San Francisco,Denver,Dallas |            1500 |
| San Francisco |   Denver |                 San Francisco,Denver |            1000 |
| San Francisco |  Chicago |  San Francisco,Denver,Dallas,Chicago |            2100 |
| San Francisco | New York | San Francisco,Denver,Dallas,New York |            3500 |

Problem

We have the following Oracle table: ``` CREATE TABLE graph ( company VARCHAR2(10) , from VARCHAR2(15) , to VARCHAR2(15) , cost NUMBER(18,2)); ``` With the following data: ``` INSERT INTO graph VALUES('Lufthansa', 'San Francisco', 'Denver', 1000); INSERT INTO graph VALUES('Lufthansa', 'San Francisco', 'Dallas', 10000); INSERT INTO graph VALUES('Lufthansa', 'Denver', 'Dallas', 500); INSERT INTO graph VALUES('Lufthansa', 'Denver', 'Chicago', 2000); INSERT INTO graph VALUES('Lufthansa', 'Dallas', 'Chicago', 600); INSERT INTO graph VALUES('Lufthansa', 'Dallas', 'New York', 2000); INSERT INTO graph VALUES('Lufthansa', 'Chicago', 'New York', 3000); INSERT INTO graph VALUES('Lufthansa', 'Chicago', 'Denver', 2000); ``` We are asked to create a table: ``` CREATE TABLE paths ( from VARCHAR2(15) , to VARCHAR2(15) , minimal_cost NUMBER);` ``` Where a row in table `paths` should indicate that "I can reach `X` from `Y` and in the lowest cost `C`. What I've tried so far: ``` INSERT INTO paths ("from", "to") SELECT DISTINCT CONNECT_BY_ROOT "from" AS "From", "to" AS "To" FROM graph START WITH "from" in (SELECT "from" FROM graph) CONNECT BY NOCYCLE PRIOR "to" = "from"; ``` (I have renamed table names and attributes from my language, so there might be syntax errors if you try to run the statements directly.) To above statement creates duplicates in almost every way. Also, I've got no idea, how `cost` should be computed. Do I need to create a `PL/SQL` procedure? Does Oracle support these kind of queires?

Original source