Постановка задачи
Пусть дан граф 
дугам которого приписаны веса (стоимости), задаваемые
матрицей C = [cij].
дозаданной конечной вершины 
, при условии, что такой путь существует, т.е. при условии 
. Здесь 
- множество, достижимое из вершины s. Элементы 
матрицы весов С могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с отрицательным суммарным весом. Если такой цикл все же существует и 
- некоторая его вершина, то, двигаясь от s к , обходя затем цикл достаточно большое число раз и попадая, наконец, в t,мы получим путь со сколь угодно малым весом, означающим, что кратчайшего пути не существует. Следующие задачи являются обобщениями сформулированной выше задачи о кратчайшем пути.
1. Для заданной начальной вершины s найти кратчайшие пути между s и всеми другими вершинами 
.
2. Найти кратчайшие пути между всеми парами вершин.
На практике часто требуется найти не только кратчайший путь, но также второй, третий и т.д. кратчайшие пути в графе. Располагая этими результатами, можно решить, какой путь выбрать в качестве наилучшего (указанный подход полезен при использовании таких критериев, которые являются субъективными по своей природе или не могут быть непосредственно включены в алгоритм).
Источник:
Теория графов. Лекция. 2017
Еще по теме Постановка задачи:
-
Аналитическая геометрия -
Вариационное исчисление -
Векторный и тензорный анализ -
Высшая геометрия -
Высшая математика -
Вычислительная математика -
Дискретная математика -
Дифференциальное и интегральное исчисление -
Дифференциальные уравнения -
Исследование операций -
История математики -
Комплексное исчисление -
Линейная алгебра -
Линейное программирование -
Математическая логика -
Математическая физика -
Математический анализ -
Пределы -
Ряды -
Статистика -
Теория вероятностей -
Теория графов -
Теория игр -
Теория принятия решений -
Теория случайных процессов -
Теория чисел -
Финансовая математика -
Функциональный анализ -
-
Антропология -
Астрономия -
Безопасность жизнедеятельности -
Библиотечное дело -
Биология -
Военное дело -
География -
Зоология -
История -
Культурология -
Литература -
Математика -
Медицина -
Педагогика -
Политология -
Право России -
Право України -
Психология -
Религоведение -
СМИ и журналистика -
Социология -
Технические науки -
Транспорт -
Физика -
Философия -
Финансы -
Экология -
Экономика -
Этнография и демография -
Юриспруденция -
Языкознание -