Question 9: Shortest paths [10]

Show the output from the following algorithm, assuming it was run on the graph below. (All edges in the graph are bidirectional.)

Algorithm
=========
Initialize the Distance matrix as follows:
   Distance[i][j] = 0 if i == j
   Distance[i][j] = w if there is an edge of
                         weight w from i to j
   Distance[i][j] = infinity otherwise

for each possible intermediate node (N1 to N3)
    for each possible source vertex (N1 to N3)
        for each possible destination vertex (N1 to N3)
            if the distance from source to destination is 
               greater than the sum of the distances from
                  source to intermediate and
                  intermediate to destination
            then update the source-to-destination distance
                 AND PRINT THE SOURCE/DESTINATION NODE IDS
                     AND DISTANCES BETWEEN THEM

Graph
=====
     N1
    /  \
  8/    \5
  /      \
N2--------N3
     10