Введение. 
Графы. Поиск кратчайшего пути из заданной вершины в заданную

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

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

Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.

Если ребра не имеют ориентации, граф называется неориентированным.

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

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

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