Branch-and-bound algoritmen med estimert gjenværende avstand
Mål: finne korteste sti fra S til G i en graf.
- La Q være en kø med ett element: stien av lengde null fra S til S.
- Gjenta inntil Q er tom eller inntil første stien i Q terminerer i G:
- La s være første stien i Q, fjern s fra Q; dann nye stier
s1,s2,... ved å utivde s langs kanter fra siste node i s.
- Fjern alle nye stier som inneholder løkker.
- Legg alle gjenværende stier til Q.
- Sorter Q med hensyn på summen av sti-lengde pluss et under-estimat av gjenstående avstand til G, la stiene med minst kostnad være først i Q.
- Hvis G ble nådd, rapporter den billigste stien til G
(første sti i Q), ellers rapporter at G ikke kan nås fra S.
Siden er skrevet at Inge Jonassen, vennligst
send en melding til inge@ii.uib.no dersom du oppdager
feil eller har andre kommentarer ellers spørsmål.