Поиск кратчайших путей в графе

Задача поиска кратчайших путей в графе (Shortest Path Problem), заключается в следующем:

Заданы n вершин графа (узлов сети) $v_1,v_2,\ldots,v_n$ и целые длины дуг $d_{ij} \equiv d(v_i,v_j)$ между ними. Чему равна наименьшая возможная длина пути, ведущего из v₁ в v_k, для всех $k \in (2 \ldots n)$?

Если длины дуг неотрицательны, то можно использовать алгоритм Дейкстры, если есть отрицательные длины, но нет циклов отрицательного веса (если такие циклы есть — то оптимального решения очевидно не существует), то можно использовать алгоритм Флойда-Уоршолла.
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.