Metoda relaksacji

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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').