Percorso minimo sorgente singola

Percorso più breve della singola sorgente?

Poiché con Matrix Multiplication è possibile eseguire tutte le coppie con il percorso più breve e la singola sorgente è un sottoinsieme per tutte le coppie, è anche possibile il percorso più breve della singola sorgente. Ignora semplicemente le altre coppie.

Algoritmo basato su moltiplicazione di matrici

1. Considerare la moltiplicazione della matrice di adiacenza ponderata con se stessa - tranne, in questo caso, sostituiamo l'operazione di moltiplicazione nella moltiplicazione di matrici per addizione e l'operazione di addizione per minimizzazione
2. Si noti che il prodotto della matrice di adiacenza ponderata con se stesso restituisce una matrice che contiene i percorsi più brevi di lunghezza 2 tra qualsiasi coppia di nodi
3. Da questo argomento risulta che A ⁿ contiene tutti i percorsi più brevi
4. A ⁿ è calcolato mediante raddoppiamenti di potenza - cioè, come A, A ² , A ⁴ , A ⁸ , ...
5. Abbiamo bisogno delle moltiplicazioni della matrice log (n), ognuna delle quali richiede un tempo O (n ³ )
6. La complessità seriale di questa procedura è O (n ³ log (n))
7. Questo algoritmo non è ottimale, poiché gli algoritmi più noti hanno complessità O (n ³ )