Algoritmer til de store grafer: Den korteste vej fra A til B

En dansk datalog har fundet den mest effektive metode til at finde den korteste vej i et netværk, der hele tiden ændrer sig.
ING.DK: At finde den korteste eller hurtigste rute fra ét sted til et andet er både big business, uhyre anvendeligt og et matematisk udfordrende problem. Et specielt og relevant problem er, hvor hurtigt man kan finde en ny, hvis den oprindelige rute blokeres.
Vil du have fuld adgang til DataTech?

DataTech skriver til dig, der arbejder professionelt med data og analytics. Vi giver dig inspirerende cases, nyheder og debat om alt fra Machine Learning-modeller til dataetik.

Prøv DataTech gratis

DataTech giver dig ny viden, cases og erfaringer med at lykkes med AI og data science i praksis. Få 3 ugers gratis og uforpligtende prøveabonnement

Klik her
Eksempel på beregning af korteste vej med Dijkstras algoritme

 I dette eksempel har vi en graf med 9 knuder og 14 kanter og ønsker at bestemme den korteste vej fra 0 til enhver af de øvrige knuder.
Dijkstras algoritme begynder i 0 og gennemsøger alle knuder for at komme frem til en reduceret graf, der udeluk-kende viser de korteste veje fra 0 til enhver af de andre knuder.

Det følgende er en forenklet og ikke fuldstændig korrekt gengivelse af Dijkstras algoritme. Den går gradvist frem og begynder med at fjerne kanten mellem 1 og 7, da den direkte vej fra 0 til 7 er kortere end vejen via 1. Da afstanden til 8 er den samme via 6 som direkte fra 7, kan vi også fjerne kanten mellem 7 og 8.

grafik ingeniøren
Illustration: Ingeniøren

Hermed kommer vi frem til dette mellemresultat, hvor vejene til de grønne knuder (1, 6 og 7) er fastlagt, mens vejene til de viste røde knuder og videre frem endnu ikke er bestemt.

Ingeniøren grafik
Illustration: Ingeniøren


Dernæst undersøges kanterne fra knuderne 2, 5 og 8, og grafen opdateres. Endelig undersøges kanterne, der går til 3 og 4. Det fører slutteligt frem til denne graf, der angiver de korteste veje fra 0 til enhver anden knude. Den oprindelige graf havde kredse, hvor man i princippet kunne bevæge sig i rund-kreds, som fra 6 til 7 til 8 til 6 osv. Det er ikke muligt i den endelige version, som i fagterminologien kaldes en rettet acyklisk graf eller en DAG for directed acyclic graph.

Ingeniøren grafik
Illustration: Ingeniøren


Ved ruteplanlægning kan man komme ud for, at kanternes vægt ændrer sig (det tager længere tid at komme frem, fordi der er kø), eller en kant helt forsvinder (vejen er lukket). Hvis kanten mellem 5 og 6 ovenfor forsvinder, kan vi ikke komme frem til hverken 4 eller 5. Der skal beregnes en ny rute, som bliver beskrevet ved grafen til venstre, hvor algoritmen igen benytter kanten mellem 2 og 5, der tidligere var blevet udeladt.

Store O-notationen

Inden for datalogi benytter man den såkaldte store O-nota­tion til at beskrive kompleksiteten af en beregning.

Lad os antage, at vi har et problem, hvor løsningstiden vokser som funktion af inputtets størrelse på denne måde T(n) = 73n³ + 221n² + 58.

For store n er det kun tredje­potensleddet, der har betydning, ja selv faktoren 73 foran tredjepotensleddet har ikke den store betydning. Vi siger, at T(n) asymptotisk set (for store n) ikke vokser hurtigere end n³. Det skriver vi som T(n) = O(n³).

I andre situationer kan der indgå en logaritmeafhængig i udtrykket, så vi f.eks. har O(n³log⁴n). I den såkaldte O-tilde notation (Õ), ser man også bort fra disse log n-faktorer og skriver Õ(n³) i stedet for O(n³log⁴n).