在有向图中找到所有不同的路径并计算最小成本。

Question

在有向图中找到所有不同的路径并计算最小成本。

3

我们有以下的 Oracle 表格：

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

以下是相关数据：

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);

我们被要求创建一个表格：

CREATE TABLE paths
( from VARCHAR2(15)
, to VARCHAR2(15)
, minimal_cost NUMBER);`

在表格paths中的一行应该表示“我可以以最低成本C从Y到达X。”

到目前为止，我尝试过：

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";

我已经将表名和属性名从我的语言进行了更名，因此如果您尝试直接运行这些语句可能会出现语法错误。

上述语句几乎以所有方式创建了重复项。此外，我不知道如何计算cost。我需要创建一个PL/SQL过程吗？Oracle是否支持这些类型的查询？

- Dyin

你期望的输出是什么？ - Rachcha

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MT0 · Accepted Answer

通过对 SYS_CONNECT_BY_PATH 的稍加运用以及使用正则表达式从列表中提取数字的函数，您可以做到：

SQL Fiddle

Oracle 11g R2模式设置：

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;
/

查询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"

结果:

|          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 |

同时，这还能为每对目的地获取最佳路线：

查询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"

结果：

|          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 |

以下是一个纯SQL的解决方案：

查询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"

结果:

|          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 |