algorytm dijkstry

Odpowiedz Nowy wątek
2014-12-23 21:29
0

Witam serdecznie, potrzebuję porady - ponieważ nie wiem czy dobrze zrozumiałem algorytm, a mam do zrobienia program semestralny w oparciu o niego.
Przykładowe miasta( Program ma wczytać je z tekstu, dowolną ilość )
Szczecin Poznan 220
Szczecin Koszalin 110
Poznan Bytom 300
Poznan Lodz 130
Lodz Katowice 170
Bytom Katowice 15
Bytom Wroclaw 180

Na wyjściu po wybraniu któregoś z miast, ma wyskoczyć lista miast, dzięki któremu możemy się tam dostać jak najkrótszą drogą.
Przeczytawszy opracowania tego algorytmu, albo źle go zrozumiałem - albo dobrze zrozumiałem i tak tak go mm interpretować.
W każdym opracowaniu, była mowa o grafie(coś ala "mapa") i na jej podstawie były wyliczane najkrótsze droga z punktu A do D.
Więc mógłby mi ktoś proszę powiedzieć, czy program mam pisać jakoś o oparciu o ten graf, chociaż o ile jestem w stanie sobie wyobrazić napisanie go, mając gotowy już graf, tak nie jestem juz w stanie tego pojąc, jak go napisać mając o wiele więcej miast.

Z góry dziękuję za pomoc.

Pozdrawiam
Wesołych świąt :)

Pozostało 580 znaków

2014-12-23 21:38
0

Nie bardzo cię rozumiem. Wybranie jednego miasta to chyba trochę mało? Może jednak wybierasz dwa miasta między którymi wyznaczasz trasę? Tak czy siak algorytm Dijkstry zwraca ci najkrótsze odległości od wybranego wierzchołka (miasta) do wszystkich pozostałych. A twojego drugiego pytania w ogóle nie rozumiem. Każde miasto to wierzchołek grafu, każda para podana na wejściu to krawędź a odleglość to waga tej krawędzi.

Podsumowując: gdzie jest problem?


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

Pozostało 580 znaków

2014-12-23 21:48
0

Na wstępie wprowadzam dowolną ilość dwóch miast, podając między nimi odległość. Po wklepaniu miast(bądź wczytaniu z pliku) podaje jedno miasto i program ma wyświetlić najkrótszą odległość, do każdego miasta, jeżeli jest taka mozliwość.
Tak wygląda treść całego semestralnego zadania: http://screenshooter.net/101726245/nyvcwun
Tak jak wspomniałem, zrozumiałem algorytm, ale nie rozumiem jak mam go użyć w oparciu o mój program, więc to jest mój główny problem - bo nie wiem po prostu czy dobrze zrozumiałem ten algorytm.

Dzięki za odpowiedź : )

Pozostało 580 znaków

2014-12-23 21:54

Zadanie semestralne? Serio? o_O Nie żeby coś, ale my dostawaliśmy takie zadania do stuknięcia w 30 min na kolokwium na 2 semestrze studiów...
Tak czy siak, napisałem już wyżej jak należy to zrobić.

  • czytasz z wejścia dane i tworzysz sobie z nich graf
  • wczytujesz miasto źrodłowe
  • odpalasz Dijsktrę (w trakcie relaksacji wierzchołka oczywiście oprócz aktualnie minimalnej sumy wag na dojście do tego wierzchołka zapisujesz także informacje o tym skąd tam przyszedłeś, tzn jaki jest poprzedni wierzchołek na ścieżce)
  • wypisujesz ścieżki uzyskane w Dijkstrze zwyczajnie idąc sobie od końca, tzn dla każdego wierzchołka który nie jest źródłem odczytujesz sobie informacje o "poprzednim" wierzchołki (tą którą zapisaliśmy sobie wyżej) i tak aż trafisz na źródło
    Na oko to jest 20 min pisania, 30 jeśli nie znasz Dijkstry i musisz doczytać na wikipedii jak implementować.

Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.
edytowany 1x, ostatnio: Shalom, 2014-12-23 21:54

Pozostało 580 znaków

2014-12-23 22:03
0

No właśnie jedyny problem będę mieć z "czytasz z wejścia dane i tworzysz sobie z nich graf" Z resztą sobie poradzę, tylko czy mógłbyś odnieść się z jakąś wskazówką konkretnie do tego podpunktu?
Dzieki za pomoc :)

Pozostało 580 znaków

2014-12-23 22:16
1

Przecież już to napisałem o_O
Wczytujesz dane z wejścia. Każde wczytane miasto to wierzchołek grafu. Każda wczytana z wejścia linijka w postaci
Miasto1 Miasto2 Odległość
to krawędź ''Miasto1-Miasto2 o wadze Odległość"
Więc czytasz sobie po linijce i po każdej wczytanej linijce wrzucasz sobie podane Miasta do zbioru wierzchołków a parę razem z wagą to zbioru krawędzi.
Graf składa sie z wierzchołków i krawędzi. Co jeszcze ci tu potrzebne?


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.
edytowany 1x, ostatnio: Shalom, 2014-12-23 22:17

Pozostało 580 znaków

2014-12-23 22:20
0

Nic, teraz zrozumiałem :)
Dzięki

Pozostało 580 znaków

2014-12-25 18:11
0

Witam,
jeżeli mogę jeszczę tylko zapytać o jedną podpowiedź, to wczytywanie tych miast wraz z odległością najlepiej będzie zrobić listą jednokierunkową? Od wczoraj przeszukuje internet i głowię się jak zrobić to najłatwiej i najbardziej ekonomicznie.
Chyba, że przez wczytywanie tych miast i odległości z pliku należy to zrobić inaczej?
Z góry dziękuję za odpowiedź.
Pozdrawiam

Pozostało 580 znaków

2014-12-25 19:05
1

Nie, wczytanie zrobić scanf'em w pętli.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2014-12-25 19:37
0

Przyznam, że takiej odpowiedzi się nie spodziewałem i zbiłeś mnie całkowicie z tropu. Czyli nie muszę tutaj z niczym kombinować, po prostu utworzyć trzy tablice? Jedna odpowiadająca za miasto1,druga za miasto2 i trzecia za odległość?
Przepraszam, jeżeli moje pytania są zbyt banalne i zawracają tyłko niepotrzebnie głowe :)

Pozostało 580 znaków

2014-12-25 19:39
1

poczytaj o strukturach i listach nawlekanych.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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