Narzędzie do analizy teorii grafów online
Oblicz najkrótszą ścieżkę w grafie nieskierowanym z wagami. Wpisz krawędzie, wybierz wierzchołki i poznaj odległość oraz trasę.
Rozpocznij
Funkcje i możliwości narzędzia
Narzędzie analizuje grafy nieskierowane z wagami nieujemnymi. Obsługuje do 1000 krawędzi i 500 wierzchołków. Krawędzie mogą być równoległe (wiele krawędzi między tymi samymi wierzchołkami). Wagi są domyślnie równe 1, jeśli nie podano inaczej. Algorytm Dijkstry znajduje najkrótszą ścieżkę między wskazanymi wierzchołkami.
Przykład działania
Dla krawędzi: A,B,2, B,C,3, A,C,10 i trasy od A do C, narzędzie zwróci odległość 5 i ścieżkę A → B → C.
Ograniczenia
Narzędzie nie obsługuje grafów skierowanych, wag ujemnych, wizualizacji współrzędnych, centralności, minimalnych drzew rozpinających ani algorytmów dla krawędzi ujemnych. Nie wylicza również wszystkich równorzędnych najkrótszych ścieżek ani składowych spójności.
Lista kontrolna przed użyciem
- Sprawdź, czy każda krawędź jest w formacie
start,koniec,waga. - Upewnij się, że wagi są nieujemne (zero jest dozwolone).
- Zweryfikuj, że wierzchołki startowy i końcowy istnieją na liście krawędzi.
- Pamiętaj, że krawędzie są nieskierowane – kolejność wierzchołków nie ma znaczenia.
Najczęstsze pytania (FAQ)
1. Co oznacza komunikat o braku połączenia?
Oznacza, że w grafie nie istnieje ścieżka między wskazanymi wierzchołkami – graf jest niespójny w tym zakresie.
2. Czy mogę użyć wag ujemnych?
Nie, algorytm Dijkstry wymaga wag nieujemnych. Wagi ujemne spowodują błąd.
3. Jak traktowane są krawędzie równoległe?
Krawędzie równoległe są dozwolone. Algorytm uwzględni wszystkie, wybierając najkrótszą ścieżkę.
Oddzielaj pola przecinkami ASCII, a w wagach używaj kropki dziesiętnej. A,B oznacza wagę 1; A,B, jest obecnie czytane jako 0, więc wpisuj wagę jawnie. Puste wiersze są pomijane. Nazwy rozróżniają wielkość liter; usuwane są tylko zewnętrzne odstępy, a przecinki są zabronione. Ten sam początek i koniec daje odległość 0 i ten wierzchołek jako ścieżkę. Liczone są wszystkie wymienione wierzchołki. Sumy zmiennoprzecinkowe mogą być zaokrąglane; osiągalna odległość poza skończonym zakresem wywołuje błąd liczbowy.
Przetwarzanie odbywa się lokalnie w przeglądarce.