Kortaste vägen(genom x antal noder)[/Mod]

Jag har tänkt skriva ett program som beräknar kortaste vägen mellan x antal noder. Noderna är positioner som bestäms utav koordinater. Har riktat in mig på Dijkstras algoritm men vet inte riktigt hur jag ska implementera den.

Problemet är att det inte alltid är fågelvägen som är mest effektiv på grund av hur vägarna är dragna. Någon som har tips?

Googlar du "dijkstras python" så hittar du kod för detta. Utöver det ser jag inte riktigt vad tråden ska gå ut på om du inte postar vad du har gjort själv.

A*Star är populärt, finns mängder av olika också, är ju populära i spel.

Dijktras algoritm är ju en sådan algoritm som man bör ha ritat med penna och papper innan man kollar på pseudokoden och börjar med implementeringen.

Jag kan rekommendera videon i Princetons fria algoritmkurs "Algorithms II" på http://coursera.org. De använder visserligen Java men de ger åtminstone en fullständig och korrekt beskrivning av Dijkstras algoritm, till skillnad från många Youtube-videos.

Det kom också nyligen ut en illustrerad algoritmbok på Manning förlag som heter "Grokking Algorithms". Jag har bara bläddrat i den, men den kan vara värd att kolla upp. Den ägnar ett helt kapitel åt Dijktras algoritm, och alla kodexempel är skrivna i Python.

Just Dijkstra's algoritm är en sån där algoritm jag ville minnas det fanns tusentals exempel på överallt, men bara ett fåtal av exemplen var faktiska korrekta implementationer. Var skitfrustrerande ville jag minnas eftersom det var en så pass trivial implementation men så få meningsfulla exempel.

Du får väl sätta lämpliga vikter på de olika sträckorna (kanterna). Vilket blir lite jobbigt då det inte räcker att bara räkna ut avstånden med hjälp av koordinaterna.

Dijkstras algoritm fungerar utmärkt. Koordinaterna för respektive nod spelar ingen som helst roll för att finna den kortaste vägen - det är endast kanternas vikter du ska ta i åtanke.

Koordinaterna kan du förstås ha nytta av om du ämnar visualisera något, men låt det vara tills din implementation av vald algoritm är på plats.