рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Задача о кратчайшем пути

Задача о кратчайшем пути - раздел Охрана труда, Алгоритм поиска кратчайших расстояний в графе Как Кратчайшим Путем Попасть Из Одной Вершины Графа В Другую? В Терминах Прои...

Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число – время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.7).

Рис.7. Исходные данные к задаче о кратчайшем пути.

Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл.8).

Табл.8. Исходные данные к задаче о кратчайшем пути.

Начало дуги Конец дуги Время в пути

Задача: как кратчайшим путем попасть из вершины 1 в вершину 4?

Решение. Введем обозначение: С(Т) – длина кратчайшего пути из вершины 1 в вершину Т. Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается. Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис.7 и в табл.6, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3)=1. Кроме того, очевидно, что С(1)=0. В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение С(4)=min{С(2)+4; С(5)+5}.

Таким образом, проведена реструктуризация задачи – нахождение С(4) сведено к нахождению С(2) и С(5). В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение С(5)=min{С(3)+2; С(6)+3}. Мы знаем, что С(3)=1. Поэтому С(5)=min{3; С(6)+3}. Поскольку очевидно, что С(6) – положительное число, то из последнего соотношения вытекает, что С(5) =3. В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение С(2)=min{С(1)+7; С(3)+5; С(5)+2}. Нам известно, что С(1)= 0, С(3 =1, С(5)=3. Поэтому С(2) =min{0+7; 1+5 ; 3+2}=5.

Теперь мы можем найти С(4): С(4)=min{С(2)+4 ; С(5)+5}=min{5+4; 3+5}=8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1.

Итак, кратчайший путь таков: 1 → 3 → 5 → 4 .

Задача о кратчайшем пути для конкретных исходных данных (рис.7 и табл.6) полностью решена.

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

– Конец работы –

Эта тема принадлежит разделу:

Алгоритм поиска кратчайших расстояний в графе

Алгоритм поиска кратчайших расстояний в графе... Алгори тм Де йкстры... Задача о кратчайшем пути...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Задача о кратчайшем пути

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Алгори́тм Де́йкстры
Это алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгор

Задача о максимальном потоке
Каким маршрутом послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена? Для решения этой задачи

Задача линейного программирования при максимизации потока
Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть ХKM – объем перевозок из пункта К в пункт М. Согласно рис.8 К = 0,1,2,3, М = 1,2,3,

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги