Analizzatore di Teoria dei Grafi

Analisi del percorso più breve

Questo strumento risolve il problema del cammino minimo in un grafo non orientato con pesi non negativi. È utile per capire come funziona l'algoritmo di Dijkstra e per verificare calcoli in contesti educativi o di pianificazione.

Esempio concreto

Inserisci i seguenti archi:

A,B,2
B,C,3
A,C,10

Imposta come nodo di partenza A e come arrivo C. Il tool restituirà:

Distanza: 5
Percorso: A → B → C

Il percorso diretto A-C avrebbe peso 10, ma passando da B si ottiene 2+3=5, che è il minimo.

Parametri e limiti

• Numero massimo di archi: 1000.
• Numero massimo di nodi distinti: 500.
• Pesi non negativi: i pesi negativi vengono rifiutati, ma gli archi con peso zero sono ammessi.
• Gli archi sono non orientati: un arco A,B vale anche per B,A.
• Eventuali archi paralleli sono consentiti.
• Il tool non supporta grafi diretti, visualizzazione di coordinate, centralità, alberi di copertura minimi o algoritmi con pesi negativi.

Domande frequenti

Come vengono gestiti i pesi omessi?

Se non specifichi il peso, viene assunto pari a 1. Ad esempio, la riga A,B equivale a A,B,1.

Perché il tool rifiuta pesi negativi?

Perché utilizza l'algoritmo di Dijkstra, che non funziona correttamente con archi di peso negativo. Per grafi con pesi negativi servirebbe un algoritmo diverso, non supportato.

Il tool mostra tutti i percorsi più brevi?

No, mostra un solo percorso (quello trovato dall'algoritmo). Non elenca percorsi alternativi con la stessa distanza.