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'). Kategoria:Teoria grafów