For shortest path you can use either a modified Roy-Floyd algorithm (pretty elaborate solution) either the classical backtracking approach; with good stopping conditions you may get an answer in reasonable time.
For minimum spanning tree you can try using Kruskal algorithm.
Make a Google search for the names, it might help if you want all kinds of details. It's been a while since I last used Kruskal, but it is a good and fast enough algorithm, especially if you have already the Adj. Mat. [red]Nosferatu[/red]
We are what we eat...
There's no such thing as free meal...
once stated: methane@personal.ro