В чем разница между задачами нахождения кратчайшего и максимального пути в графе?

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

Задача о кратчайшем пути — это поиск пути между двумя точками (вершинами) на графе, в котором минимизируется сумма весов рёбер, составляющих путь. ru.wikipedia.org Например, в GPS-навигаторах осуществляется поиск кратчайшего пути между точкой отправления и точкой назначения. ru.ruwiki.ru ru.wikipedia.org

Задача о максимальном пути (или о самом длинном пути) — это поиск простого пути максимальной длины в заданном графе. ru.wikipedia.org Путь называется простым, если в нём нет повторных вершин. ru.wikipedia.org Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. ru.wikipedia.org

Таким образом, кратчайшая задача ориентирована на поиск минимального пути, а максимальная — на поиск пути максимальной длины.