Кратчайший путь из u в v – это любой путь p из u в v, для которого w(p) = δ(u, v), где:

• w(p) = сумма весов всех ребер пути p
• δ(u, v) = min{w(p): по всем путям p из u в v}, если существует путь u в v; ∞ - в противном случае

Любая часть кратчайшего пути сама есть кратчайший путь. Это значит, что задача о кратчайших путях обладает свойством оптимальности для подзадач - признак того, что к ней может быть применимо динамическое программирование или жадный алгоритм.

Техника релаксации состоит в следующем. Для каждого ребра v V храним некоторое число
d[v], являющееся верхней оценкой веса кратчайшего пути из s в v. Начальное значение оценки кратчайшего пути и массива π устанавливается процедурой:

Initialize-Single-Source(G, s)

for(i=0;i<n;i++)
	{
		dv[i]=65535; //65535 - бесконечность
	}
	dv[xn]=0;

Релаксация ребра (u, v) E состоит в следующем: значение d[v] уменьшается до d[u] + ω(u, v); при этом d[v] остается верхней оценкой. Мы хотим, чтобы значение π[v] указывало путь, использованный при получении этой верхней оценки, поэтому одновременно мы меняем значение
π[v]:

Relax(G, s)

 if (d[v] > (d[u] + ω[u, v]))
	{
 	d[v] = d[u] + ω[u, v];
	π[v]= u;
	}

На рисунке приведены два примера релаксации: в одном случае оценка кратчайшего пути уменьшается (а), в другом ничего не происходит (б).