se dici in quel modo certo ke funziona... ma usi una matrice piena simmetrica... sprechi un po' l'algoritmo.. a quel punto usa un Kruskal.. ke in nlogn ti risolve tutto x grafo xkè il dikstra ogni volta considera pure l'arco di ritorno.. tra 2 vertici.. ma poi nn lo prende mai xkè nn gli conviene... gli archi hanno peso positivo x l'istanza del problema, cmq ho fatto la prova a mano sul tuo grafo, e mi funziona l'algo, te come fai a farti stampare la soluzione ? magari c'è un errore nella procedura di visualizzazione, inoltre mi veniva un albero... ti do il vettore dei padri ke mi è venuto a me:

0 1 2 3
- 3 0 0

0 è la radice e la riga sopra sono i vertici, e sotto ogni vertice c'è il padre