Задача
Формальная постановка задачи кратчайших путей выглядит так: имеется на- правленный граф G = (V, E) с обозначенным начальным узлом s. Предполагается, что в графе существует путь от s к любому другому узлу G. Каждому ребру e назна- чена длина le > 0, которая обозначает время (или расстояние, или затраты), необхо- димое для перемещения по e. Для пути P длина P (обозначаемая l(P)) вычисляется как сумма длин всех ребер, входящих в P. Наша задача — определить кратчайший путь от s к каждому из других узлов графа. Следует упомянуть, что хотя задача сформулирована для направленного графа, случай ненаправленного графа обе- спечивается простой заменой каждого ненаправленного ребра e = (u, v) длины ie двумя направленными ребрами (u, v) и (v, u), каждое из которых имеет длину ie.
Еще по теме Задача:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения