<<  DiscreteMath`ComputationalGeometry` 
<<  DiscreteMath`Combinatorica`
<< 
      Graphics`Animation`

EdgeSort[ e_List,  
        ew_List ]  := 
Module [{i,  minIndex,  
          x  =  e,  xw  =  ew,  j, key, 
          key2 }, 
Do[{ 
key  =  
              xw[[i]]; 
key2  =  
              x[[i]]; 
 
            j  =  i  -  
                1; 
While[ ( j  >  0 )  &&  ( 
                  xw[[j]]  >  key ),  ( 
                xw[[j + 1]]  =  xw[[j]];  
                x[[j + 1]]  =  
                  x[[j]];  j-- )]; 
xw[[j + 
                    1]]  =  
              key;  
x[[j + 1]]  =  
              key2;
}, 
{i,  2,  
            Length[x]}]; 
x
]

Convert[ 
        e_List ]  := 
Module [{i,  minIndex,  
          x  =  e[[1]],  x1  =  e[[2]],  
          m  =  {}}, 
Do[{ 
m  =  
              Append[ m,  { i,  
                  x[[i]] } ]
}, 
{i,  1,  Length[x]}]; 
m   =  
          EdgeSort[m,  
            x1 ]; 
m
]

\(\(\(drawDij[\ 
        x_Graph\ ]\)\(\ \)\(:=\)\(
\)\(Module[\ {shortfile, \ data\  = \ x, \ a, \ b, \ c, \ f, \ h, \ g\ }, 
b\  = \ 
          Dijkstra[x, 1]; 
h\  = \ 
          ShortestPathSpanningTree[x, \ 
            1]; 
g\  = \ {{1}}; 
c\  = \ 
          Convert[b]; 
shortfile\  = 
Table[
Graphics[\ {
Rectangle[\ {0, 0}, \ {0.8, \ 
                    0.8}, 
ShowGraph[\ 
                    Highlight[\ h, \ 
                      g\ \  = \ 
                        Append[
                          g, \ \ {c[\([t + 
                                  2]\)]}], \ {HighlightedEdgeColors\  -> \ {Green}, \ HighlightedVertexColors\  -> \ {Yellow}, \ 
                        HighlightedVertexStyle\  -> \ Disk[Normal]}], \ 
                    PlotLabel\  -> \ "Dijkstra's algorithm", \ 
EdgeColor -> Gray, \ 
                    TextStyle\  -> \ {FontSize\  -> \ 15, \ 
                        FontColor -> Purple}, \ 
                    Graphics\ ]], 
\ 
                Text["www.combinatorica.com", \ {0.5, 
                    0.0}, \ {TextStyle -> {FontColor -> 
                          Red}}]\ }, 
{\ 
                ImageSize -> 350, \ 
                AspectRatio -> 
                  1}
]
, \ {t, \ 0, \ 
              V[h] - 2, \ 
              1}]; \ 
shortfile
]\)\(\ \)\)\)

ShowGraph[
      a  =  Graph[{{{1, 23}}, {{1, 42}}, {{1, 12}}, {{1, 35}}, {{2, 
                8}}, {{2, 38}}, {{2, 19}}, {{2, 24}}, {{3, 11}}, {{3, 
                26}}, {{3, 17}}, {{3, 13}}, {{3, 31}}, {{3, 39}}, {{4, 
                9}}, {{4, 47}}, {{4, 29}}, {{4, 30}}, {{5, 40}}, {{5, 
                32}}, {{5, 35}}, {{5, 16}}, {{5, 50}}, {{5, 7}}, {{5, 
                30}}, {{5, 29}}, {{6, 33}}, {{6, 28}}, {{6, 41}}, {{6, 
                34}}, {{6, 32}}, {{6, 40}}, {{7, 30}}, {{7, 50}}, {{7, 
                21}}, {{8, 43}}, {{8, 44}}, {{8, 38}}, {{8, 24}}, {{8, 
                15}}, {{9, 15}}, {{9, 24}}, {{9, 36}}, {{9, 18}}, {{9, 
                46}}, {{9, 47}}, {{10, 43}}, {{10, 48}}, {{10, 27}}, {{10, 
                25}}, {{10, 20}}, {{10, 26}}, {{10, 49}}, {{11, 49}}, {{11, 
                26}}, {{11, 39}}, {{11, 19}}, {{12, 21}}, {{12, 14}}, {{12, 
                35}}, {{12, 42}}, {{13, 17}}, {{13, 20}}, {{13, 25}}, {{13, 
                42}}, {{13, 23}}, {{13, 31}}, {{14, 35}}, {{14, 21}}, {{14, 
                16}}, {{15, 24}}, {{16, 35}}, {{16, 21}}, {{16, 50}}, {{17, 
                26}}, {{17, 20}}, {{18, 36}}, {{18, 46}}, {{19, 24}}, {{19, 
                38}}, {{19, 49}}, {{19, 39}}, {{19, 37}}, {{19, 41}}, {{19, 
                28}}, {{20, 25}}, {{20, 26}}, {{21, 50}}, {{22, 25}}, {{22, 
                27}}, {{22, 48}}, {{22, 43}}, {{23, 45}}, {{23, 31}}, {{23, 
                42}}, {{23, 35}}, {{24, 28}}, {{24, 36}}, {{25, 42}}, {{25, 
                27}}, {{26, 49}}, {{27, 48}}, {{28, 41}}, {{28, 33}}, {{28, 
                36}}, {{29, 47}}, {{29, 40}}, {{29, 30}}, {{31, 39}}, {{31, 
                45}}, {{32, 34}}, {{32, 37}}, {{32, 45}}, {{32, 35}}, {{32, 
                40}}, {{33, 46}}, {{33, 36}}, {{33, 40}}, {{34, 41}}, {{34, 
                37}}, {{35, 45}}, {{36, 46}}, {{37, 39}}, {{37, 45}}, {{37, 
                41}}, {{38, 44}}, {{38, 49}}, {{39, 45}}, {{40, 47}}, {{40, 
                46}}, {{43, 48}}, {{43, 49}}, {{43, 44}}, {{44, 49}}, {{46, 
                47}}}, {{{0.8763203891958579, 0.18642657610911217}, 
              VertexWeight -> 
                Euclidean[
                  1, {0.8763203891958579, 
                    0.18642657610911217}]}, {{0.0938727932145889, 
                0.7235623922913812}, 
              VertexWeight -> 
                Euclidean[
                  2, {0.0938727932145889, 
                    0.7235623922913812}]}, {{0.31151029177589096, 
                0.28301919150915067}, 
              VertexWeight -> 
                Euclidean[
                  3, {0.31151029177589096, 
                    0.28301919150915067}]}, {{0.9470337669457384, 
                0.9375011503987436}, 
              VertexWeight -> 
                Euclidean[
                  4, {0.9470337669457384, 
                    0.9375011503987436}]}, {{0.7879957870488687, 
                0.6985685826314445}, 
              VertexWeight -> 
                Euclidean[
                  5, {0.7879957870488687, 
                    0.6985685826314445}]}, {{0.516394186468163, 
                0.6707540443922319}, 
              VertexWeight -> 
                Euclidean[
                  6, {0.516394186468163, 
                    0.6707540443922319}]}, {{0.9959369874550299, 
                0.6751347926564338}, 
              VertexWeight -> 
                Euclidean[
                  7, {0.9959369874550299, 
                    0.6751347926564338}]}, {{0.07513402369885687, 
                0.7298162984905522}, 
              VertexWeight -> 
                Euclidean[
                  8, {0.07513402369885687, 
                    0.7298162984905522}]}, {{0.33091260599639655, 
                0.9416011204351705}, 
              VertexWeight -> 
                Euclidean[
                  9, {0.33091260599639655, 
                    0.9416011204351705}]}, {{0.21107814743499975, 
                0.15080310172608974}, 
              VertexWeight -> 
                Euclidean[
                  10, {0.21107814743499975, 
                    0.15080310172608974}]}, {{0.300625342896293, 
                0.38561381487684687}, 
              VertexWeight -> 
                Euclidean[
                  11, {0.300625342896293, 
                    0.38561381487684687}]}, {{0.9520696687257488, 
                0.24447890768715458}, 
              VertexWeight -> 
                Euclidean[
                  12, {0.9520696687257488, 
                    0.24447890768715458}]}, {{0.4243049537004351, 
                0.19918723876773467}, 
              VertexWeight -> 
                Euclidean[
                  13, {0.4243049537004351, 
                    0.19918723876773467}]}, {{0.85819687551116, 
                0.5209165153957734}, 
              VertexWeight -> 
                Euclidean[
                  14, {0.85819687551116, 
                    0.5209165153957734}]}, {{0.11279466192454414, 
                0.916168047258584}, 
              VertexWeight -> 
                Euclidean[
                  15, {0.11279466192454414, 
                    0.916168047258584}]}, {{0.9111631085654216, 
                0.5834153649970298}, 
              VertexWeight -> 
                Euclidean[
                  16, {0.9111631085654216, 
                    0.5834153649970298}]}, {{0.3247988748756754, 
                0.2175994646271395}, 
              VertexWeight -> 
                Euclidean[
                  17, {0.3247988748756754, 
                    0.2175994646271395}]}, {{0.39476892209725856, 
                0.9126613206047979}, 
              VertexWeight -> 
                Euclidean[
                  18, {0.39476892209725856, 
                    0.9126613206047979}]}, {{0.3288618874206454, 
                0.5424646719707057}, 
              VertexWeight -> 
                Euclidean[
                  19, {0.3288618874206454, 
                    0.5424646719707057}]}, {{0.31963489839840165, 
                0.18284502211424578}, 
              VertexWeight -> 
                Euclidean[
                  20, {0.31963489839840165, 
                    0.18284502211424578}]}, {{0.9979492814242489, 
                0.6008635515355353}, 
              VertexWeight -> 
                Euclidean[
                  21, {0.9979492814242489, 
                    0.6008635515355353}]}, {{0.10855675096340191, 
                0.03204192038815604}, 
              VertexWeight -> 
                Euclidean[
                  22, {0.10855675096340191, 
                    0.03204192038815604}]}, {{0.6973239385279558, 
                0.2152497366586884}, 
              VertexWeight -> 
                Euclidean[
                  23, {0.6973239385279558, 
                    0.2152497366586884}]}, {{0.15648708223765304, 
                0.7875630127010015}, 
              VertexWeight -> 
                Euclidean[
                  24, {0.15648708223765304, 
                    0.7875630127010015}]}, {{0.2730189848275208, 
                0.016062497890953712}, 
              VertexWeight -> 
                Euclidean[
                  25, {0.2730189848275208, 
                    0.016062497890953712}]}, {{0.29829020672649303, 
                0.266646497305228}, 
              VertexWeight -> 
                Euclidean[
                  26, {0.29829020672649303, 
                    0.266646497305228}]}, {{0.16022432290297664, 
                0.09989445063236972}, 
              VertexWeight -> 
                Euclidean[
                  27, {0.16022432290297664, 
                    0.09989445063236972}]}, {{0.38712709816107144, 
                0.6832311323081982}, 
              VertexWeight -> 
                Euclidean[
                  28, {0.38712709816107144, 
                    0.6832311323081982}]}, {{0.8354254480273012, 
                0.8822949860052303}, 
              VertexWeight -> 
                Euclidean[
                  29, {0.8354254480273012, 
                    0.8822949860052303}]}, {{0.9923581760638129, 
                0.7705698117034003}, 
              VertexWeight -> 
                Euclidean[
                  30, {0.9923581760638129, 
                    0.7705698117034003}]}, {{0.5065635606066559, 
                0.3398303140345245}, 
              VertexWeight -> 
                Euclidean[
                  31, {0.5065635606066559, 
                    0.3398303140345245}]}, {{0.6727232776654113, 
                0.5877247895891545}, 
              VertexWeight -> 
                Euclidean[
                  32, {0.6727232776654113, 
                    0.5877247895891545}]}, {{0.508614279182407, 
                0.7389667624989893}, 
              VertexWeight -> 
                Euclidean[
                  33, {0.508614279182407, 
                    0.7389667624989893}]}, {{0.5641665267020093, 
                0.5556828692009984}, 
              VertexWeight -> 
                Euclidean[
                  34, {0.5641665267020093, 
                    0.5556828692009984}]}, {{0.811290340654451, 
                0.5237170258403009}, 
              VertexWeight -> 
                Euclidean[
                  35, {0.811290340654451, 
                    0.5237170258403009}]}, {{0.4076794444643563, 
                0.768119856499997}, 
              VertexWeight -> 
                Euclidean[
                  36, {0.4076794444643563, 
                    0.768119856499997}]}, {{0.5382713558269303, 
                0.5076545279493472}, 
              VertexWeight -> 
                Euclidean[
                  37, {0.5382713558269303, 
                    0.5076545279493472}]}, {{0.10938923773786327, 
                0.501473359194769}, 
              VertexWeight -> 
                Euclidean[
                  38, {0.10938923773786327, 
                    0.501473359194769}]}, {{0.3780470329239537, 
                0.40776007731697744}, 
              VertexWeight -> 
                Euclidean[
                  39, {0.3780470329239537, 
                    0.40776007731697744}]}, {{0.7222621395767919, 
                0.8182422268865708}, 
              VertexWeight -> 
                Euclidean[
                  40, {0.7222621395767919, 
                    0.8182422268865708}]}, {{0.5426215848966524, 
                0.5254650913117472}, 
              VertexWeight -> 
                Euclidean[
                  41, {0.5426215848966524, 
                    0.5254650913117472}]}, {{0.7299039635129789, 
                0.04767241518317054}, 
              VertexWeight -> 
                Euclidean[
                  42, {0.7299039635129789, 
                    0.04767241518317054}]}, {{0.03605802428999656, 
                0.18563477727722272}, 
              VertexWeight -> 
                Euclidean[
                  43, {0.03605802428999656, 
                    0.18563477727722272}]}, {{0.057180685847567705, 
                0.45994762559401603}, 
              VertexWeight -> 
                Euclidean[
                  44, {0.057180685847567705, 
                    0.45994762559401603}]}, {{0.5274437451075896, 
                0.4466680147782335}, 
              VertexWeight -> 
                Euclidean[
                  45, {0.5274437451075896, 
                    0.4466680147782335}]}, {{0.4930141591455584, 
                0.9042647563930176}, 
              VertexWeight -> 
                Euclidean[
                  46, {0.4930141591455584, 
                    0.9042647563930176}]}, {{0.7161534044531385, 
                0.9229509889379326}, 
              VertexWeight -> 
                Euclidean[
                  47, {0.7161534044531385, 
                    0.9229509889379326}]}, {{0.08533471468120207, 
                0.13614489989302056}, 
              VertexWeight -> 
                Euclidean[
                  48, {0.08533471468120207, 
                    0.13614489989302056}]}, {{0.17788204862620816, 
                0.41529646098858547}, 
              VertexWeight -> 
                Euclidean[
                  49, {0.17788204862620816, 
                    0.41529646098858547}]}, {{0.9759454769433388, 
                0.6346715406982516}, 
              VertexWeight -> 
                Euclidean[
                  50, {0.9759454769433388, 
                    0.6346715406982516}]}}]]

a  =  
      SetEdgeWeights[a,  WeightingFunction -> Euclidean]

ShowAnimation[drawDij[ a]]