Odległości między miejscowościami. Optymalny sposób reprezetacji.

Na potrzeby projektu na studiach modeluję bazę danych połączeń kolejowych. Natrafiłem na problem, nie wiem w jaki sposób optymalnie zapisywać odległości między miejscowościami. Mój aktualny pomysł to utworzenie nowego zbioru encji "Odległości" w której przechowywał bym klucze do dwóch stacji (najbliższych sobie) oraz dzielącą je odległość. Znając przebieg trasy docelowej byłbym w stanie wyliczyć sumaryczną długość trasy, sumując poszczególne odcinki.

Jednak to rozwiązanie wydaje mi się dość skomplikowane do późniejszej realizacji. Obliczenie długości trasy z wieloma przystankami wymagać będzie wielu zapytać pośrednich, a tego chyba lepiej unikać.

Znacie jakiś inny, lepszy sposób reprezentacji odległości ?

wg mnie to jest optymalne rozwiązanie. A co do obliczania odległości to albo funkcja w bazie albo (o ile baza wspiera) to funkcja okna zwracająca poprzedni/następny rekord i tyle

To co opisałeś to realizacja relacji połączenia bezpośredniego pomiędzy stacjami.

Można się zastanowić czy nie warto stworzyć jeszcze jednej relacji typu jeden do wielu pomiędzy połączeniem kolejowym, a stacjami występującymi na tym połączeniu, z dwoma atrybutami relacj - kolejnością oraz odległością od stacji początkowej. Tj. połączenie kolejowa zawiera stacje kolejowe w danej kolejności o dnych odległościach od stacji początkowej.

Podczas tworzenia nowych połączeń odległości na trasie byłby uzupełniane na podstawie bezpośrednich połączeń, o których wspomniałeś. W ten sposób obliczneie odległości na trasie będzie wymagało mniej zapytań, wytsraczy sprawdzić jaka jest odległości do stacji docelowej i odjąć od niej odległość względem początku trasy od stacji na której wsiada pasażer.

Może ktoś robił takie rzeczy praktycznie i się wypowie.

Problem najkrótszej ścieżki w grafie (z tego co pamięam to algorytm "zachłanny"). Opisany na wikipedii
Albo np. tu: http://aprogrammerwrites.eu/?p=1391#.WeDEK4PTNPY

Marcin.Miga napisał(a):

Problem najkrótszej ścieżki w grafie (z tego co pamięam to algorytm "zachłanny"). Opisany na wikipedii
Albo np. tu: http://aprogrammerwrites.eu/?p=1391#.WeDEK4PTNPY

Fajnie, też go znamy. Ale chyba nie o to mu chodziło xD

Piotr Biesek napisał(a):

[...] Obliczenie długości trasy z wieloma przystankami wymagać będzie wielu zapytać pośrednich, a tego chyba lepiej unikać.

Cały problem jest złożony, ale jeśli chodzi o realizację tego w jednym zapytaniu, to tu problemu nie widzę:

select sum(odleglosc) from odcinki o
where o.id in (..., ..., ...)