Рассмотрим сеть G=(J,U) с одним источником S и одним стоком T. В сети n вершин. В вершину S не входит ни одна дуга, а из вершины T не выходит ни одна дуга. Пронумеровать в такой сети вершины правильно необходимо, чтобы в сети не было контуров.

Рангом вершины i назовем max число дуг в пути, которое связывает источник – вершину S, с данной вершиной i.

Правильной считается такая нумерация вершин в сети, при которой все номера вершин r-го ранга будут меньше номеров вершин (t+1)-го ранга. Существует разные способы правильной нумерации вершин в сети. Рассмотрим одни из них, который называется методом вычеркивания дуг.

Исходной вершине сети, т.е. источнику присваиваем номер 1. Затем вычеркнем (удалим) все дуги выходящие из вершины 1. После этого в сети окажутся конечное число вершин без входящих дуг. Назовем эти вершины, вершины 1-го ранга и присвоим ми в произвольном порядке номера 2,…,k₁. Затем вычеркнем (удалим) все дуги, выходящие из верши 1-го ранга. В сети опять окажется конечное число вершин без входящих дуг. Назовем их вершинами 2-го ранга и присвоим им в произвольном порядке номера k₁+1,…,k₂.

И т.д., процесс нумерации вершин прекращается тогда, когда будет пронумерована последняя вершина сети – сток.

Кротчайшим путь такой сети можно найти с помощью метода Форда.

Пример.

Дана сеть с одним источником S=1 и стоком T. В сети нет контуров. Число на дугах (i,j) означают их длины l_ij.