Budowa bazy, algorytm, sieć kolejowa

0

Hej. Pisze program, który będzie się poruszał po bazie danych zawierającej dane o połączeniach miedzy miastami. Planowałem zaplanować to tabelami. 1 tabela = 1 linia kolejowa. 3 kolumny w każdej: 1: id_stacji, 2: nazwa_stacji, 3: odległość km od 1 stacji w danej linii.

opis: Mamy dla przykładu linie kolejowa Warszawa-Łódź:

[row_index][id_stacji][nazwa_stacji][odleglosc]

0 056 Warszawa Wschodnia 0
1 057 Warszawa Centralna 5
2 058 Warszawa Zachodnia 10
3 079 Żyrardów 45
4 041 Skierniewice 70

7 012 Łódź Fabryczna 122

Ale takich linii chciałbym dodać o wiele więcej, a co więcej linie będą się krzyżowały, czyli np:
dodam połączenia:

Warszawa Wschodnia - Łowicz Głowny (nie przez skierniewice)
Skierniewice - Łowicz Głowny (nie przez warszawę)

Więc już mamy kółeczko.
Tak samo inne, kiedy w połowie trasy dochodza inne linie.

Funkcjojalność:

Chcę, aby po wpisaniu do programu stacji koncowej i poczatkowej, sprawdzało mi, czy dane połączenie istnieje, ew liczyło odległość na podtsawie ostatniej kolumny.

Akceptuje jako algorytm rozwiazania planu bazy danych inny model połączeń. Jak ktoś ma jakiś pomyśł, zapraszam do podzielenia się

Pozdrawiam.

0
  1. stacje
    id
    nazwa
    lokalizacja

  2. trasy
    id
    nazwa

  3. stacja-trasa
    id_stacji
    id_trasy
    nr (numer stacji na trasie, żeby kolejność była)
    odleglosc (odległość od poprzedniej) - łatwo wyliczysz odległość między dwoma stacjami na trasie
    czas_przejazdu (czas przejazdu od poprzedniej stacji, jak odległość)

to tak z gróbsza

0

hmm, a jak bedzie wygladało przykladowe wyszukanie:

mamy 3 trasy laczace sie:

Gdynia główna - Malbork
Malbork - Elbląg
Elbląg - Olsztyn

Dajać na wejsiu Gdnie gł i Olszytn, w jaki sposób zobrazuje to nasze wyszukanie?

0

zauważ, że równie dobrze można złożyć trasę, która będzie leciała przez Warszawę, Zakopane i Wrocław :). Chyba jedynym rozwiązaniem bedzie stworzenie z wszystkich stacji grafu skierowanego i wyszukanie w nim najkrótszej drogi

0

Ja nie siedzę w bazach, więc pierw poczytam o grafach skierowanych, a później się zabiorę do zadania.
Właśnie taki miałem cel, stworzenie bazy danych o stacjach, i na podstawie tego chce wyciągać wszystko, co tylko mogę. Stacje pośrednie, ilości km, itp

thx, jak bede miał jakieś pytania, dam znać

0

@Misiekd napisał

zauważ, że równie dobrze można złożyć trasę, która będzie leciała przez Warszawę, Zakopane i Wrocław

I tak bywa, strona www.pkp.pl na pytanie o pociąg z Rogoźna (miasteczko na pólnoc od Poznania, około 40km, linia Poznań-Koszalin) do Poznania zaproponowała taką podróż:
Rogoźno-Piła (około 50 km, dokładnie w strone przeciwną)
Piła-Krzyż około 60km
Krzyż Poznań ok. 80km
dwie przesiadki i prawie 5 razy dalej, połączenie bezpośrednie istniało również

0
Misiekd napisał(a)

zauważ, że równie dobrze można złożyć trasę, która będzie leciała przez Warszawę, Zakopane i Wrocław :). Chyba jedynym rozwiązaniem bedzie stworzenie z wszystkich stacji grafu skierowanego i wyszukanie w nim najkrótszej drogi

Poczytałem o owych grafach, tylko wiedza ta nie pozwala mi na zastosowanie tego w praktyce.
Wierchołkami takiego grafu mają byc stacje, na ktorcyh trasa się rozgałęzia, tak?
Jak dalej moge zaimpelentowac schemat grafu skierowanego w tym przypadku. Stworzyłem juz przykładowe tabele, wg schematu pdoanego wyżej, ale nie wiem jak mam tam zastosowa graf skierowany.

Za wskazówki będę wdzięczny.

0

http://www.algorytm.org/index.php?option=com_content&task=view&id=91&Itemid=28

wierzechołki to stacje, krawędzie to połączenia między stacjami a wagi to (w zależności co Cię interesuje)
a) odległości między stacjami,
b) czas przejazdu między stacjami

generalnie jak masz już graf to szukasz najkrótszej drogi między konkretnymi wierzchołkami z uwzględnieniem typu pociągu

0

a jak przełożyc tabele ze stacjami/trasami na graf skierowany?

0

masz tabelkę ze stacjami, masz tabelkę z połączeniami - przeczytać i złożyć z tego graf

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