Requete recursive - Graphe - Chemin le plus court

Version imprimable

Bonjour

J'ai un problème pour définir ma requete à partir de la table ci après et de ces enregistrements :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 create table route ( villedep varchar(15), villearr varchar(15), distance number(5) check (distance>=0), primary key(villedep,villearr) ) / insert into route values('paris','lille',200); insert into route values('paris','nantes',500); insert into route values('paris','strasbourg',500); insert into route values('paris','bordeaux',700); insert into route values('paris','lyon',400); insert into route values('paris','marseilles',800); insert into route values('lille','nantes',500); insert into route values('lille','strasbourg',500); insert into route values('strasbourg','lyon',300); insert into route values('nantes','bordeaux',300); insert into route values('lyon','marseille',300);
En faite, à partir de cela je dois formuler une requête permettant de définir le plus court chemin d'une ville à l'autre ainsi qu'une autre selectionnant les villes se trouvant à k kilometres d'une ville donnée ?

Je ne vois pas du tout comment je peux arriver à un tel résultat. Si vous avez quelques pistes à me donner je suis preneur.

Merci pour votre aide. Nico

Pour la seconde, c'est assez simple :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
WITH route AS (
SELECT 'paris'AS villedep,'lille' villearr,200 distance FROM DUAL UNION ALL
SELECT 'paris','nantes',500 FROM DUAL UNION ALL
SELECT 'paris','strasbourg',500 FROM DUAL UNION ALL
SELECT 'paris','bordeaux',700 FROM DUAL UNION ALL
SELECT 'paris','lyon',400 FROM DUAL UNION ALL
SELECT 'paris','marseilles',800 FROM DUAL UNION ALL
SELECT 'lille','nantes',500 FROM DUAL UNION ALL
SELECT 'lille','strasbourg',500 FROM DUAL UNION ALL
SELECT 'strasbourg','lyon',300 FROM DUAL UNION ALL
SELECT 'nantes','bordeaux',300 FROM DUAL UNION ALL
SELECT 'lyon','marseille',300 FROM DUAL)
SELECT DECODE(villedep, 'lille', villearr, villedep) AS ville
FROM route
WHERE (villedep = 'lille' AND distance = 500)
	OR
	 (villearr = 'lille' AND distance = 500)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
create or replace function eval(value varchar2)
return number is
  n number;
begin
  if (translate(value,'x+-*/.0123456789','x') is not null)
  then
    raise_application_error(-20001,'Invalid input');
  end if;
  execute immediate 'select '||value||' from dual' into n;
  return n;
end;
/

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
with t as (
  select
    decode(x,1,villedep,villearr) villedep,
    decode(x,1,villearr,villedep) villearr,distance
  from
    route,
    (select 1 x from dual union all select 2 from dual)
)
select
  villedep,
  villearr,
  min(distance) distance,
  min(p) keep (dense_rank first order by distance) p
from (
  select
    connect_by_root villedep villedep,
    villearr,
    eval(sys_connect_by_path(distance,'+')) distance,
    sys_connect_by_path(villedep||'-'||villearr,'/') p
  from
    t
  connect by nocycle villedep=prior villearr
)
where villedep!=villearr
group by villedep,villearr
order by 1,2;

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
VILLEDEP        VILLEARR          DISTANCE P
--------------- --------------- ---------- --------------------------------------------------
bordeaux        lille                  800 /bordeaux-nantes/nantes-lille
bordeaux        lyon                  1100 /bordeaux-paris/paris-lyon
bordeaux        marseille             1400 /bordeaux-paris/paris-lyon/lyon-marseille
bordeaux        marseilles            1500 /bordeaux-paris/paris-marseilles
bordeaux        nantes                 300 /bordeaux-nantes
bordeaux        paris                  700 /bordeaux-paris
bordeaux        strasbourg            1200 /bordeaux-paris/paris-strasbourg
lille           bordeaux               800 /lille-nantes/nantes-bordeaux
lille           lyon                   600 /lille-paris/paris-lyon
lille           marseille              900 /lille-paris/paris-lyon/lyon-marseille
lille           marseilles            1000 /lille-paris/paris-marseilles
lille           nantes                 500 /lille-nantes
lille           paris                  200 /lille-paris
lille           strasbourg             500 /lille-strasbourg
lyon            bordeaux              1100 /lyon-paris/paris-bordeaux
lyon            lille                  600 /lyon-paris/paris-lille
lyon            marseille              300 /lyon-marseille
lyon            marseilles            1200 /lyon-paris/paris-marseilles
lyon            nantes                 900 /lyon-paris/paris-nantes
lyon            paris                  400 /lyon-paris
lyon            strasbourg             300 /lyon-strasbourg
marseille       bordeaux              1400 /marseille-lyon/lyon-paris/paris-bordeaux
marseille       lille                  900 /marseille-lyon/lyon-paris/paris-lille
marseille       lyon                   300 /marseille-lyon
marseille       marseilles            1500 /marseille-lyon/lyon-paris/paris-marseilles
marseille       nantes                1200 /marseille-lyon/lyon-paris/paris-nantes
marseille       paris                  700 /marseille-lyon/lyon-paris
marseille       strasbourg             600 /marseille-lyon/lyon-strasbourg
marseilles      bordeaux              1500 /marseilles-paris/paris-bordeaux
marseilles      lille                 1000 /marseilles-paris/paris-lille
marseilles      lyon                  1200 /marseilles-paris/paris-lyon
marseilles      marseille             1500 /marseilles-paris/paris-lyon/lyon-marseille
marseilles      nantes                1300 /marseilles-paris/paris-nantes
marseilles      paris                  800 /marseilles-paris
marseilles      strasbourg            1300 /marseilles-paris/paris-strasbourg
nantes          bordeaux               300 /nantes-bordeaux
nantes          lille                  500 /nantes-lille
nantes          lyon                   900 /nantes-paris/paris-lyon
nantes          marseille             1200 /nantes-paris/paris-lyon/lyon-marseille
nantes          marseilles            1300 /nantes-paris/paris-marseilles
nantes          paris                  500 /nantes-paris
nantes          strasbourg            1000 /nantes-lille/lille-strasbourg
paris           bordeaux               700 /paris-bordeaux
paris           lille                  200 /paris-lille
paris           lyon                   400 /paris-lyon
paris           marseille              700 /paris-lyon/lyon-marseille
paris           marseilles             800 /paris-marseilles
paris           nantes                 500 /paris-nantes
paris           strasbourg             500 /paris-strasbourg
strasbourg      bordeaux              1200 /strasbourg-paris/paris-bordeaux
strasbourg      lille                  500 /strasbourg-lille
strasbourg      lyon                   300 /strasbourg-lyon
strasbourg      marseille              600 /strasbourg-lyon/lyon-marseille
strasbourg      marseilles            1300 /strasbourg-paris/paris-marseilles
strasbourg      nantes                1000 /strasbourg-lille/lille-nantes
strasbourg      paris                  500 /strasbourg-paris

29/10/2007, 10h45
laurentschneider

note que pour aller de Marseille à MarseilleS, 1500 km ça fait beaucoup :mrgreen:
31/10/2007, 23h26
nicottin

Merci c'était vraiment pas evident.
Le truc de la fonction eval fallait y penser de toute facon je pense qu'on était obligé pas d'autres solutions

Merci encore
++

j'avais bien essayé une fois avec lpad, mais c'est pas très extensible...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
WITH t AS (
  SELECT
    decode(x,1,villedep,villearr) villedep,
    decode(x,1,villearr,villedep) villearr,distance
  FROM
    route,
    (SELECT 1 x FROM dual union ALL SELECT 2 FROM dual)
)
SELECT
  villedep,
  villearr,
  min(distance)
FROM (
  SELECT
    connect_by_root villedep villedep,
    villearr,
 length(replace(sys_connect_by_path(lpad('.',distance,'.'),'/'),'/')) distance
  FROM
    t
  connect BY nocycle villedep=prior villearr
)
WHERE villedep!=villearr
GROUP BY villedep,villearr
ORDER BY 1,2
/

07/11/2007, 22h02
nicottin

Sinon tu peux m'expliquer ce que fait :

Code:

min(p) keep (dense_rank first ORDER BY distance) p

Merci
08/11/2007, 00h33
McM

Ca prend le premier p ramené par le select trié par distance croissante.