Найти самый короткий путь из одной вершины в другую или посчитать их количество? Это просто!

Найти длину кратчайшего пути из вершины A в вершину F. Длины путей между вершинами на иллюстрации обозначены числами.

Универсальный алгоритм поиска кратчайшего пути во взвешенном графе. Особенно полезен в том случае, когда вершин достаточно много и пути сложно проследить визуально. Назван в честь описавшего его нидерландского учёного Эдсгера Вибе Дейкстры (1930 - 2002).

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

Из всех невычеркнутых вершин берём ту, у которой написано наименьшее число (если таких несколько, берём любую). Рассматриваем все пути, которые соединяют её с невычеркнутыми вершинами, и возле каждой из них пишем, за сколько суммарно можно туда добраться через рассматриваемую. Важно: если у вершины, куда мы пробуем попасть, уже написано число, его нужно заменить, если на текущем шаге получается меньшее значение - мы нашли более короткий путь. После такого рассмотрения текущая вершина вычёркивается.

Продолжаем выполнять шаг 2 до тех пор, пока у конечной вершины не окажется наименьшее число или пока она не останется единственной невычеркнутой. Листайте картинки для того, чтобы проследить ход выполнения алгоритма.

У конечной вершины записан ответ.

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

Будем возле каждой вершины писать количество способов попасть туда из исходной, а возле каждого ребра - количество способов пройти по нему, выйдя из исходной вершины. Очевидно, что возле всех рёбер, выходящих из исходной вершины, должна быть написана единица. Поскольку в вершины B и C другие дороги не ведут, в каждую из них можно попасть единственным способом.

Поскольку в B и C можно попасть единственным способом, значит, по всем рёбрам, которые из них выходят, тоже можно пройти единственным способом. Теперь можно определить количество способов попасть в вершину D путём сложения чисел на всех рёбрах, которые в неё ведут - это 1 + 1 + 1 = 3.

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

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

Здесь многие пытаются вычёркивать вершины, через которые путь точно не пройдёт. А зря. Это не всегда возможно сделать (хотя конкретно в этой задаче можно, но не стоит), и приводит к ошибкам в ответе. Достаточно рассмотреть общую схему, представленную на первой иллюстрации, и убедиться, что путь в этой задаче всегда будет выглядеть как A - H, а затем H - K. Таким образом, достаточно посчитать по уже известному алгоритму количество путей из A в H, затем отдельно из H в K и полученные ответы перемножить - для любого из первых маршрутов подойдёт и любой второй. Листайте картинки для того, чтобы проследить ход выполнения алгоритма. Ответ в этой задаче - 8.

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

В этом случае всё ещё проще. Нельзя проходить через D? Берём чёрную гелевую ручку, вычёркиваем вершину D, а также все рёбра, с которыми она соединена. На иллюстрации они просто удалены из графа. Дальше задача решается уже известным способом - только вдвое короче. Листайте картинки для того, чтобы проследить ход выполнения алгоритма. Здесь ответ будет равен 7.