관계를 기반으로 두 객체 간의 최단 경로 얻기

-2

이 문제를 해결하기 위해 SQL 또는 C# 중 가장 좋은 방법을 찾으려고합니다. 약 50 개 정도의 개체 목록을 가지고 있다고 가정 해 봅시다. 각 개체는 두 개의 다른 개체와 관련됩니다.관계를 기반으로 두 객체 간의 최단 경로 얻기

Object 1. 
ID: 1 
Name:  Aspect1 
Relation1: Aspect5 
Relation2: Aspect7 

Object 2. 
ID: 2 
Name:  Aspect2 
Relation1: Aspect23 
Relation2: Aspect50 

Object 3 
ID: 13 
Name:  Aspect13 
Relation1: Aspect5 
Relation2: Aspect23

기본적 난 50 개체를보고하고 그 사이에 3 개 연결의 최소 다른 측면을 연결하여 aspect2하는 aspect1를 연결하는 최단 경로를 찾을 필요가있다.

최종 결과는

aspect1 -- aspect5 -- aspect13 -- aspect23 -- aspect2

출처

2015-01-31 beefwipe

@GordonLinoff, 왜 이렇게 열심히일까요? –

@ GordonLinoff, 그래,하지만 여기에 제공된 문제의 일부분에 대해 당신의 포스트 벨로우 (정점의 수가 적고, 교차점의 수가 고정되어 있음)에 대답했고, 또 다른 손으로 [Dijkstra 's algorithm] (http : // en. wikipedia.org/wiki/Dijkstra%27s_algorithm#Algorithm). –

@HamletHakobyan. . . 나는 모든 정점을 방문하는 최단 경로를 생각하고 있었고 두 개를 연결하지 않았습니다. –

SQL이 문제가 이런 종류의 최적화되어 있지 않습니다 같을 것입니다. 그러나, 당신이 그렇게에 길이 4, 5의 경로를 사용해 연속 쿼리를 실행하고 있습니다 :

with relations as (
     select objectid as from_o, relation1 as to_o 
     from objects 
     union all 
     select objectid, relation2 
     from objects 
    ) 
select * 
from relations r1 join 
    relations r2 
    on r1.to_o = r2.from_o join 
    relations r3 
    on r2.to_o = r3.from_o join 
    relations r4 
    on r3.to_o = r4.from_o 
where r1.objectid = 'Aspect1' and 
     r4.objectid = 'Aspect2';

을 개체 당이 관계 50 개체, 이것은 짧은듯한 경로에 대한 풀 수있는 문제가 될 것이다. 이 쿼리가 아무 것도 반환하지 않으면 유사한 방식으로 조인을 계속 추가합니다. 데이터베이스가 with을 지원하지 않는 경우 하위 쿼리 또는 뷰를 사용하여 동일한 효과를 얻을 수 있습니다.

재귀 적 CTE를 사용하여이를 해결하는 방법이 있습니다. 그러나 데이터베이스를 지정하지 않으며 모든 데이터베이스가 데이터베이스를 지원하는 것은 아닙니다.

출처

2015-01-31 15:54:22

downvote에 대한 이유가 있습니까? –

이것이 작동 할 것이라고 생각합니다. 감사합니다. – beefwipe

@beefwipe. . . 더 짧은 경로가 간섭하지 않도록하려면'r2.objectid <> 'Aspect2'와 r3.objectid <> 'Aspect3 ''을'where' 절에 추가하십시오. –

관계를 기반으로 두 객체 간의 최단 경로 얻기

답변

관련 문제