Metoda relaksacji

Relaksacja krawędzi – sprawdzenie, czy przy przejściu daną krawędzią grafu (u,v) z ‘u’ do ‘v’, nie otrzymamy krótszej niż dotychczasowa ścieżki z ‘s’ do ‘v’. Jeżeli tak, to zmniejszamy oszacowanie wagi najkrótszej ścieżki d[v] gdzie:

• d[v] - oszacowanie wagi najkrótszej ścieżki,
• 'u' i 'v' - to dowolne dwa wierzchołki grafu połączone krawędzią o danej wadze,
• 's' - to wierzchołek grafu połączony z 'v' poprzez wierzchołek 'u' ('s'----'u'----'v').