vägvalsalgoritmer

Vägvalsalgoritmer är algoritmer som används för att hitta en väg mellan noder i en graf, ofta i kartor, nätverk eller spelvärldar. En väg består av en följd av kanter och har en viss kostnad eller längd. Grafer kan vara riktade eller oriktade, viktade eller obetade, och kan vara statiska eller dynamiska. Vanliga problem är att hitta kortaste vägen mellan en källa och ett mål eller att beräkna alla par av kortaste vägar.

Bland de mest använda algoritmerna finns Dijkstras algoritm, som hittar kortaste vägen i grafer med icke-negativa vikter. Denna algoritm används ofta tillsammans med en prioritetskö och har komplexitet ungefär O((V + E) log V). A* sökalgoritm är en utvidgning av Dijkstra som använder en heuristik som uppskattar hur långt det är till målet; vid en admissibel och konsekvent heuristik återfinns den optimala vägen snabbare i praxis.

Andra viktiga metoder är BFS för obetagna grafer, DFS för utforskning, Bellman-Ford som klarar negativa vikter och kan påvisa negativa cykler, samt Floyd-Warshall som beräknar alla par kortaste vägar i O(n^3). Bidirektionell sök kan accelerera sökningen genom att söka från både källa och mål.

Vägvalsalgoritmer kan implementeras med olika grafrepresentationer, såsom listor över grannar eller motsvarande matriser, och i praktiken används ofta prioriterade köer och heuristiker. Tillämpningar finns inom ruttplanering, robotnavigering, spelutveckling och nätverkstrafik.