Algorithmic Graph Theory
I'll try to give you an answer for your first question. I'll use the Combinatorica package that ships with Mathematica.
Let's initialize a Dodecahedral Graph:
<< Combinatorica`
g = DodecahedralGraph
Now show the Euclidian shortest paths from vertex 1 to all other vertices in this dodecahedral graph, using ShortestPathSpanningTree:
t = ShortestPathSpanningTree[
SetEdgeWeights[g, WeightingFunction -> Euclidean], 1];
ShowGraphArray[{g, t}, VertexStyle -> Disk[0.05], VertexNumber -> True]

Side Note:
ShortestPathSpanningTree does internally call ChooseShortestPathAlgorithm to determine whether to use Dijkstra's algorithm or Bellman-Ford.
This decision is based on the presence of negative edge weights and the sparsity of the graph.
Side Note End
You could use Floyd-Warschall shortest path algorithm as well, using Combinatorica.
Let's start by generating random integer weights and compute the matrix of shortest-path distances between pairs or vertices:
g = SetEdgeWeights[CompleteGraph[7],
WeightingFunction -> RandomInteger, WeightRange -> {0, 10}];
(s = AllPairsShortestPath[g]) // TableForm
0 1 3 1 3 4 3
1 0 2 0 2 4 3
3 2 0 2 0 2 1
1 0 2 0 2 4 3
3 2 0 2 0 2 1
4 4 2 4 2 0 3
3 3 1 3 1 3 0
Specifying the Parent tag produces parent information, in addition to the shortest-path distances. The (i,j)th entry in the parent matrix contains the predecessor of j in a shortest path from i to j:
First[AllPairsShortestPath[g, Parent]] // TableForm
0 1 3 1 3 4 3
1 0 2 0 2 4 3
3 2 0 2 0 2 1
1 0 2 0 2 4 3
3 2 0 2 0 2 1
4 4 2 4 2 0 3
3 3 1 3 1 3 0
How shorter does travel get if we take shortest path rather than direct hops?
(ToAdjacencyMatrix[g, EdgeWeight] - s) /. Infinity -> 0 // TableForm
0 7 4 0 0 0 0
7 0 7 0 0 4 0
4 7 0 5 0 7 0
0 0 5 0 7 2 6
0 0 0 7 0 0 7
0 4 7 2 0 0 6
0 0 0 6 7 6 0
I hope I've even touched what you're asking for.
P.S.: Since there is a new Graph functionality in Mathematica it is really confusing how to use them properly. I think it is time for a clean up for the next version of Mathematica.