Zadanie z analizy sieciowej

0

Szanowni,

Mam do rozwiązania zadanie z analizy sieciowej.
Sieć i tabela powiązań widoczna jest na załączniku.
Jako daną wejściową mam numer węzła w tym przypadku 104.
Moim zadaniem jest otrzymać listę ID odcinków którymi można dostarczyć towar do węzła 104 czyli A,B,C,D.
Odcinek E odpada bo ma zwrot w przeciwną stronę i może posłużyć jedynie na dostarczenie towaru do punktu 99.

Tabela zawiera informację o węźle S (startowym) i węźle K (końcowym) odcinków.

Mogę liczyć na Waszą pomoc w przygotowaniu zapytania lub funkcji która zwróci tę listę odcinków?

1

Wygląda to na graf skierowany, gdzie:
ID - krawędź
WEZEL - identyfikator wierzchołka
TYP - informacja o tym czy krawędź wychodząca/wchodząca z/do innego wierzchołka

Do głowy przychodzą mi zapytanie hierarchiczne/rekursywne (silniki Oracle, Postgres):
https://oracle-base.com/articles/misc/hierarchical-queries
https://www.postgresql.org/docs/9.1/static/queries-with.html

1) Robimy pivot tabeli do postaci ID, WEZEL_S, WEZEL_K, gdzie WEZEL_S przechowuje identyfikator węzła startowego dla krawędzi ID, zaś WEZEL_K identyfikator węzła końcowego dla tej samej krawędzi.

ID=D, WEZEL_S=103, WEZEL_K=104

2) Robimy zapytanie hierarchiczne (np. w Oracle):

select SYS_CONNECT_BY_PATH(ID,'/') sciezka from pivotTabeliWejsciowej connect by wezel_k = prior wezel_s; 

3) Filtrujemy te scieżki, które kończą się na 104.

Alternatywnie, w pivocie odwracamy krawędzie w grafie, np.

ID=D, WEZEL_S=104, WEZEL_K=103

Następnie robimy zapytanie hierarchiczne, ale takie które startuje w wierzchołku 104 (w Oraclu: START WITH WEZEL_S=104 + CONNECT BY PRIOR)

0

Bardzo dziekuję. Oto chodziło.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0