> Masz ścisłe pojęcie że dorga to droga, a rozluznij wyobraznie
No spróbujmy rozluźnić ją :)

>
> Weź takie
>
> Wszystkie drogi(krawędzie) mają atrybut kraju,wojewodztwa
> Niech graf A bedzie np takim przejsciem ze wezly wenwatrz wojewodztwa
> grafu B  staja sie jednym wezelem w calym wojewodztwie grafu A, wezly na
> granicy ktore lacza drogi wojewodzkie A staja sie wezlami granicznymi B
> reszta wezlow A z granic staje sie albo tymi wewnatrz B albo pomijasz
> cokolwiek (kwestia wyobrazni).

Ok, a co zrobić jeśli graf nie przypomina mapy? Np. gdy graf nie ma
określonego
położenia węzłów, określone jest tylko które węzły są połączone a
które nie?
Długość połączeń może być dodatnią wartością stałą albo zmienną o
jakimś rozkładzie?

> Teraz zaowaz ze musisz ustalic jakies
> kryterium dla wag miedzy wezlami granic a wezlami srodkowymi (tj
> kluczowe kwestia kalibracji i wyobrazni)
>
> Jesli w tym grafie zgrobym ktory zalozmy reprezentuje cala europe
> przeprowadzisz wyznaczaczanie drogi to zuyskasz liste wojewodztw przez
> ktore musi biec droga oraz liste wezlow granicznych miedzy wojewodzkimi
> przez ktore ona biegnie.
Tak, uzyskam, ale czy mniejszym kosztem? Stoję w punkcie źródłowym.
Sprawdzam
drogę do najbliższych państw. Skąd mogę wiedzieć w jakim państwie
leży
punkt docelowy? Nie wiem tego, bo wierzchołki w grafie nie mają
określonych
współrzędnych. Więc po dotarciu w zgrubnym grafie do węzła
reprezentującego
państwo, muszę odszukać listę wszystkich punktów w tym państwie i całą
przejrzeć? Czy jest jakiś szybszy sposób?

> Wystarczy teraz ze dla kazdego wojewodztwa przeprowadzisz wyznaczanie
> drogi od granicy do granicy na zadanych punktach.
>
> To jest duze uproszczenie idei ale dosc dobrze oddaje cel.
> Wynik takiego przeprowadzania wyznaczania najkrótszej sciezki bedzie
> rozwiazaniem suboptymalnym ale jednoczesnie tak bliskim opimum jak dobry
> bedie homeomorfizm i ustalone wagi grafu zgrubnego.
>
> Mozna robic inne przejscia np aby uzyskiwac liste krajow podrozy albo
> znaczacych drog itd

Zgadzam się dla grafu który reprezentuje punkty w przestrzeni N
wymiarowej
W grafie z podaną listą połączeń i wagami połączeń nadal nie rozumiem
jakby
to mogło pomóc. Jedyny zysk jaki widzę, to brak nastawiania głowicy
podczas
sekwencyjnego odczytywania listy najbliższych sąsiadów.

Pozdrawiam