Ориентированный граф G = (V, E) состоит из множества вершин V и множества дуг E. Вершины также называют узлами, а дуги – ориентированными ребрами. Дуга представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, а w – концом дуги.

Неориентированный граф G = (V, E) состоит из конечного множества вершин V и множества ребер E. В отличие от ориентированного графа, здесь каждое ребро (v, w) соответствует неупорядоченной паре вершин: если (v, w) – неориентированное ребро, то (v, w) = (w, v).

Вершина Х называется инцидентной ребру G, если ребро соединяет эту вершину с какой-либо другой вершиной.

В задаче о кратчайшем пути нам дан ориентированный взвешанный граф G = (V, E) с вещественной весовой функцией w: E R

Вес пути p=(v₀,v₁,...,v_k) - это сумма весов рёбер, входящих в этот путь:

Вес кратчайшего пути из u в v равен, по определению,

Кратчайший путь из u в v - это любой путь p из u в v, для которого

Граф называется вырожденным, если у него нет рёбер.

Вершины называются смежными, если существует ребро, их соединяющее.

Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные.

Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

Граф называется связным, если для любых двух вершин существует путь, соединяющий эти вершины.

Иногда веса ребер могут быть отрицательными. При этом важно, есть ли циклы отрицательного веса. Если из вершины s можно добраться до цикла отрицательного веса, то потом можно обходить этот цикл сколь угодно долго, и вес будет всё уменьшаться, так что для вершин этого цикла кратчайших путей не существует:

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

Часто требуется не просто подсчитать веса кратчайших путей, но и найти сами эти пути. Пусть G = (V, E) - заданный граф. Для каждой вершины будем помнить её предшественника . Предшественик вершины - это либо другая вершина, либо NIL. По завершении работы алгоритмов цепочка предшественников , начинающаяся с произвольной вершины v , будет представлять собой кратчайший путь из s в v , так что, если ≠ NIL, процедура Print-Path(G,s,v) напечатает кратчайший путь из s в v.

До завершения работы алгоритмов цепочки, получаемые итерациями π, не обязательно будут кратчайшими путями, но всё равно можно рассмотреть ориентированный подграф предшествования G_π = (V_π , E _π ), определенный так: вершины G_π - это те вершины G, у которых предшественник отличен от NIL, плюс исходная вершина:

V_π = {v V : π [v] ≠ NIL} {s}

E_π = {(π [v], v) E : v V_π \ {s}}

Дерево кратчайших путей с корнем в s есть ориентированный подграф G´ = (V´, E´),

где V ´ V и E ´ E , для которого:

1. V ´ - множество вершин, достижимых из вершины s,
2. G ´ является деревом с корнем s,
3. для каждого v V ´ путь из s в v в графе G ´ является кратчайшим путем из s в v в графе G .