Rešitev: Drevo najkrajših poti (SSSP) (Mathematica)

Iz MaFiRaWiki

Naloga: Drevo najkrajših poti (SSSP)

 <<DiscreteMath`Combinatorica`
 BF[l_List,s_Integer]:=Module[{n,Vo,d,p,w,ll,e,u,v,x},
     n=Max[Flatten[Map[Most,l]]];
     Vo=Range[n];
   
     d=Table[Infinity,{i,n}];
     d=ReplacePart[d,0,s];
     p=Table[" ",{i,n}];
   
     w=1;
     While[w<n,
       ll=l;
       While[Length[ll]>0,
         e=First[ll];
         ll=Rest[ll];
         u=e1;
         v=e2;
         If[dv>(du+e3),
           d=ReplacePart[d,(du+e3),v];
           p=ReplacePart[p,u,v],
           x=1]
         ];
       w=w+1];
   
     ll=l;
     While[Length[ll]>0,
       e=First[ll];
       ll=Rest[ll];
       u=e1;
       v=e2;
       If[dv>(du+e3),
         Print["Napaka,graf vsebuje negativen cikel."],
         x=1]
       ];
     Return[{p,d}]
     ]

Preizkusimo program še na primeru:

 k=Map[Append[#,Random[Integer,{-5,5}]]&,Edges[g]]
 {{1,2,-3},{1,3,4},{1,4,-4},{1,5,3},{2,3,0},{2,4,1},{2,5,-2},{3,4,2},{3,5,1},{4,5,2}}
 BF[k,1]
 {{ ,1,2,1,2},{0,-3,-3,-4,-5}}

Glej tudi

Osebna orodja