Graphs are structures consisting of nodes connected by edges. From urban roads to social networks to brain connectome, and so on, many real-world structures can be modeled as graphs. For decades It was assumed that the most efficient way to find best routes in a graph is Dijkstra’s algorithm. But it’s optimality was proven only in 2023, in a work that won best-paper award.
In 1956, Edsger Dijkstra invented his shortest-path algorithm while taking a break with his fiancée at a café in Amsterdam. With no writing accessories he figured it out in his head in 20 minutes. Later, he said “Without pencil and paper you are almost forced to avoid all avoidable complexities.” Today, Dijkstra’s algorithm finds optimal paths in everything from GPS and internet routing to energy grids and even social networks.
Here is how to find a shortest path for a point robot through a field of point obstacles (Wolfram key functions given in parentheses):
◼
  • Build Voronoi diagram of the obstacles (𝗩𝗼𝗿𝗼𝗻𝗼𝗶𝗠𝗲𝘀𝗵)
    • ◼
  • Transform Voronoi diagram into a graph (𝗚𝗿𝗮𝗽𝗵)
    • ◼
  • Make sure edges are weighted by distance (𝗘𝘂𝗰𝗹𝗶𝗱𝗲𝗮𝗻𝗗𝗶𝘀𝘁𝗮𝗻𝗰𝗲)
    • ◼
  • Find shortest path on the graph using Dijkstra (𝗙𝗶𝗻𝗱𝗦𝗵𝗼𝗿𝘁𝗲𝘀𝘁𝗣𝗮𝘁𝗵)
    • A simple Manipulate to understand a single path:
    In[]:=
    Manipulate[​​​​Module[​​{o,v,edges,weights,g,nf},​​SeedRandom[1];​​o=RandomReal[{-1,1},{n,2}];​​v=VoronoiMesh[o,{{-1,1},{-1,1}},MeshCellStyle{{1,All}{White,Opacity[.3]},_GrayLevel[.2]}];​​edges=MeshPrimitives[v,1]/.Line[{a_,b_}]UndirectedEdge[a,b];​​weights=edges/.UndirectedEdge->EuclideanDistance;​​g=Graph[edges,EdgeWeightweights];​​nf=Composition[First,Nearest[VertexList[g]]];​​​​Show[v,​​Graphics[{Red,Thickness[.004],Line[Join[{pt[[1]]},FindShortestPath[g,nf@pt[[1]],nf@pt[[2]]],{pt[[2]]}]]}],​​Epilog{Blue,Point[o]},ImageSize->500]​​],​​{{n,300},100,1000,1},​​{{pt,{{-.5,0},{.5,0}}},Locator},​​SaveDefinitions->True]
    Out[]=
    ​
    n
    A bit more elaborate Manipulate with multiple moving robots and a single target:
    In[]:=
    ClearAll[orb,orbS];​​orb[r_,p_,m_][t_]:=r{JacobiSN[4EllipticK[m](t-1/4-p),m],JacobiSN[4EllipticK[m](t-p),m]}​​SeedRandom[3];​​orbS[t_]=Table[orb[r,RandomReal[],.99][RandomChoice[{-1,1}]t],{r,.7,.95,.001}];
    In[]:=
    Manipulate​​​​Module​​o,v,edges,weights,g,nf,x0=
    5
    -2,​​SeedRandom[1];​​o=RandomReal[{-1,1},{1000,2}];​​v=VoronoiMesh[o,{{-1,1},{-1,1}},MeshCellStyle{{1,All}{White,Opacity[.55 Sin[4Pi t]^2]},_Black}];​​edges=MeshPrimitives[v,1]/.Line[{a_,b_}]UndirectedEdge[a,b];​​weights=edges/.UndirectedEdge->EuclideanDistance;​​g=Graph[edges,EdgeWeightweights];​​nf=Composition[First,Nearest[VertexList[g]]];​​​​Show[v,​​Graphics[{​​{Red,Opacity[.5],Thickness[.005],​​Line[Join[{orb[.25,0,.99][4t]},FindShortestPath[g,nf@orb[.25,0,.99][4t],nf@#],{#}]]&/@orbS[t]},​​{Green,PointSize[.01],Point[orbS[t]]},​​{Orange,PointSize[.03],Point[orb[.25,0,.99][4t]]}​​}],​​Epilog{Blue,Point[o]},PlotRangePadding->0,Background->Black,ImageSize->500]​​,​​{t,0,1},​​SaveDefinitions->True
    Out[]=
    ​
    t
    Code similar to Manipulate but generating animation with AnimationVideo:
    In[]:=
    v=Parallelize@AnimationVideo​​​​Module​​o,v,edges,weights,g,nf,x0=
    5
    -2,​​SeedRandom[1];​​o=RandomReal[{-1,1},{1000,2}];​​v=VoronoiMesh[o,{{-1,1},{-1,1}},MeshCellStyle{{1,All}{White,Thickness[.002],Opacity[.3 Sin[4Pi t]^2]},_Black}];​​edges=MeshPrimitives[v,1]/.Line[{a_,b_}]UndirectedEdge[a,b];​​weights=edges/.UndirectedEdge->EuclideanDistance;​​g=Graph[edges,EdgeWeightweights];​​nf=Composition[First,Nearest[VertexList[g]]];​​​​Rasterize[​​Show[v,​​Graphics[{​​{Red,Opacity[.5],Thickness[.005],​​Line[Join[{orb[.25,0,.99][t]},FindShortestPath[g,nf@orb[.25,0,.99][t],nf@#],{#}]]&/@orbS[t]},​​{Green,PointSize[.01],Point[orbS[t]]},​​{Orange,PointSize[.03],Point[orb[.25,0,.99][t]]}​​}],​​Epilog{Blue,PointSize[.0065],Point[o],Inset[Style["© https://x.com/superflow ",FontFamily->"Copperplate",White,Opacity[.5],30],{Right,Bottom},{Right,Bottom}]},PlotRangePadding->0,ImageSize->1080,Background->Black],​​RasterSize->1080​​]​​,​​{t,0,1},​​DefaultDuration->30,RasterSize->1080;//AbsoluteTiming

    CITE THIS NOTEBOOK

    Road network of shortest paths from multiple robots to a single target via Dijkstra's algorithm​
    by Vitaliy Kaurov​
    Wolfram Community, STAFF PICKS, December 24, 2024
    ​https://community.wolfram.com/groups/-/m/t/3343868