Кратчайшие пути

Ориентированный граф 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, для которого

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

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

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

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

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