Originariamente inviato da buonste
Ciao Santino,
la tua spiegazione è chiara ed esaustiva ma non risolve il mio problema.

I 2 algoritmi proposti (che avevo già studiato prima di aprire questo thread) non fanno al mio caso poichè quello di Dijkstra calcola il percorso minimo tra due nodi ma non prevede che si debba passare per tutti i nodi, mentre quello di Kruskal's prevede che si passi per tutti i nodi del grafo ma permettendo il passaggio per più volte dallo stesso nodo.

E' vero che nel mio primo esempio non l'ho specificato ma il peso degli archi è determinato/determinabile con il teorema di Pitagora tra un nodo e quelli nell'intorno.

Ad ogni modo apprezzo molto il tuo interesse e non voglio abusarne.

Anzi chiedo all'admin se ritiene opportuno spostare la discussione da PHP in qualche altro Forum OFF-Topic perchè la stessa si sta spostando da PHP a Ricerca Operativa e Analisi Matematica.

Grazie ancora a tutti!
Ste
guarda che nell'ultimo link ti ho scritto che c'è l'algoritmo che cerchi, l'ultimo esempio

e cmq se leggessi bene quello che ti si dice (ok, su Dijkstra mi son sbagliato), vedresti che Kruskal serve a :
Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex,
cmq ripeto, mi pare che l'algoritmo illustrato alla fine di questo articolo http://raffaelemarino.altervista.org...ui%20grafi.htm sia quello che cerchi nello specifico. Ovviamente, pure se leggi in giro, una soluzione ottima ed efficiente non è stata trovata, pseudo-ottime ed efficienti si (quell'algoritmo va a O(v^2) che non è male per valori di v non troppo grandi)

cmq si, con php c'entra poco