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ę. Przetwarzanie odbywa się loka…
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ę.
Przetwarzanie odbywa się lokalnie w przeglądarce.