Algorytm liczenia maksymalnego oddalenia

0

Witam
Poszukuję gotowego algorytmu który pozwalałby na wyznaczenie maksymalnej liczby połączeń dla danego wierzchołka w grafie

0

Jest na to co najmniej tyle algorytmów ile istnieje reprezentacji grafów, nie wspominając już o tym że temat: - "maksymalnej liczby połączeń dla danego wierzchołka" - to właściwie nie wiadomo o co biega.

0

Mam do przeanalizowania sieć tramwajową we Wrocławiu, gdzie za wierzchołek przyjmuje się przystanek. Jak że ilość przystanków jest na tyle duża że ręczne liczenie jest bardzo czasochłonne poszukuje jakiegoś algorytmu który pozwoli mi na wyznaczenie maksymalnej ilości krawędzi dla każdego wierzchołka, co następnie posłuży mi do wyznaczenia punktu centralnego oraz peryferyjnego. kierunek ruchu nie ma znaczenia. Nie znam się na programowaniu więc nie potrafię się posługiwać programistycznymi nazwami, czy tez samemu coś napisać.

0

Możę graficzna wersja trochę rozjaśni mój problem

0

No to albo zaczniesz oprować programistycznymi nazwami, albo zaczniesz pisać po polsku. Bo ja na przykład nadal nie rozumiem co to jest twoje "maksymalne oddalenie". W jaki sposób to liczysz? Co to jest "maksymalna ilośc krawędzi dla wierzchołka"? Jakich krawędzi?
Jeśli chodzi o wyznaczanie centralności to istnieją formalne matematyczne miary dla grafów, takie jak degree, betweenness, closeness (i wiele innych). Chodzi ci o którąś z nich? Bo tak na oko to może ci chodzić o betweenness -> to jest liczba najkrótszych ścieżek pomiędzy dowolnymi 2 węzłami grafu, które przechodzą przez dany wierzchołek.

Napisz nam JAK liczysz te swoje wartości ręcznie a my ci powiemy jakiego algorytmu szukasz...

0

W załączniku jest prosty graf przykładowy na podstawie którego wyjaśnię jak liczy się maksymalne oddalenie.
Graf posiada wierzchołki dajmy na ten przykład wierzchołek A dla niego maksymalne oddalenie jest równe 6 ponieważ najdalszy wierzchołek względem wierzchołka A jest oddalony o 6 krawędzi, czyli linii łączących sąsiednie wierzchołki. podobnie sytuacja ma się w przypadku punktu B z tą jednak różnica, że maksymalne oddalenie wynosi 5 ponieważ najdalszy wierzchołek od wierzchołka B znajduje się w odległości 5 krawędzi od niego. I teraz tak o ile w przypadku tak prostego grafu jest to do ogarnięcia to w przypadku grafu z 200 wierzchołkami jest to problematyczne, wyżej wymienioną czynność należny powtórzyć dla każdego wierzchołka w grafie. Podsumowując szukam najdłuższą możliwą drogę, którą da się wyznaczyć (oczywiście bez powielania tego samego punktu, droga może przechodzić tylko raz przez dany punkt) dla danego punktu. w Załączniku dodaję również graf właściwy na podstawie którego przeprowadzam analizę.

0

A jak sie mają do tego cykle? Co jeśli mogę dojść z wierzchołka A do wierzchołka B dwiema drogami i jedna z nich jest krótsza a druga dłuższa?
Bo jeśli szukasz dla każdego wierzchołka najdłuższej najkrótszej ścieżki pomiędzy tym wierzchołkiem a dowolnym innym to:
http://pl.wikipedia.org/wiki/Algorytm_Floyda-Warshalla + wybranie dla każdego wierzchołka maksa.

Ten algorytm tworzy tablicę, która dla pary wierzchołków A,B zwraca najkrótszą ścieżkę między tymi wierzchołkami. Możesz więc sprawdzić ścieżkę z A do każdego innego wierzchołka i wybrać najdłuższą, a potem powtórzyć to dla innych wierzchołków.

0

Ja nie jestem informatykiem, pojęcie o programowaniu mam raczej nikłe. Źle to ująłem ja poszukuję albo gotowego programu albo kodu. Sprecyzuję problem, bo ja potrzebuję takiego programu do analizy który wykonuje działania na ściśle określonych warunkach. Widzę że źle się zrozumieliśmy w wyniku odliczeń chciałbym dostać coś takiego, że najdalszy punkt od wierzchołka A oddalony jest o 5 krawędzi(połączeń), dla wierzchołka B najdalszy punkt oddalony jest o 4 krawędzie itd dla każdego po kolei. Chodzi mi o coś w tym stylu http://www.algorytm.org/algorytmy-grafowe/przeszukiwanie-grafu-wszerz-bfs-i-w-glab-dfs.html "Przeszukiwanie w głąb (DFS)"

0

Zaproponowany przez ciebie sposób jest jak najbardziej dobry z tym że nie wiem jak to użyć w praktyce, krótko mówiąc nie potrafię napisać kodu.

0

Więc dla każdego węzła odpalasz algorytm DSijkstry (ponieważ krawędzie nie mają wag to można również DFS lub A+) i wyznaczasz z tych minimalnych dróg co on znajdzie maksymalną drogę.
Skoro graf nie jest skierowany to można na zmniejszyć ilość odpaleń Dijkstry o jeden węzeł, z tym że tak mała oszczędność raczej nie warta sporej komplikacji algorytmu.

0

@Krwawy Mleczarz dla trywialnego przypadku z nieskierowanym i nieważonym grafem to wszytko jest jeden pies, czy odpalisz sekwencyjnie Dijkstre/Bellmana Forda/BFS czy odpalisz Floyda-Warshalla czy Johnsona. Efekt będzie taki sam a implementacja dość podobna.

Jeśli chodzi o gotowe narzędzie to pewnie wisi z setka takich w internecie, wystarczy poszukać po nazwach algorytmów.

0

Dziękuje za wyjaśnienie problemu. Jest jeden problem potrzebowałbym jednak algorytm który pozwoli na wyszukiwanie najdłuższej ścieżki w grafie dla danego punktu.

0

Nie potrafisz znaleźć maksimum w tablice?

0

albo mam zły tok myślenia albo nie potrafię się dobrze posługiwać tymi algorytmami bo jeżeli dobrze zrozumiałem oraz wywnioskowałem na podstawie własnych spostrzeżeń podczas zabawy algorytmami to jeżeli mam dwie możliwe drogi dojścia pomiędzy punktem A i B to zostanie przez algorytm wybrana ta krótsza, natomiast ja chciałbym żeby wybrał tę dłuższą. Znajdywanie najkrótszej drogi byłoby pomocne jeżeli miałbym maksymalnie 2 możliwe drogi pomiedzy punktami ale jeżeli możliwości jest kilka to nie ułatwia mi to pracy.

0

No to przeciez o to pytałem! A co jak masz cykl w grafie?

0

Wg mnie chodzi o najdłuższą z najkrótszych.

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