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

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 NUMBERAS  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   costsGROUP 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_costFROM   costsGROUP 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   costsGROUP 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 |