Реферат: Нахождение кратчайшего пути
- Задача об упаковках и покрытиях
оптимизация структуры ПЗУ
размещение диспетчерских пунктов городской транспортной сети
- Раскраска в графах
распределение памяти в ЭВМ
проектирование сетей телевизионного вещания
- Связность графов и сетей
проектирование кратчайшей коммуникационной сети
синтез структурно-надежной сети циркуляционной связи
анализ надежности стохастических сетей связи
- Изоморфизм графов и сетей
структурный синтез линейных избирательных цепей
автоматизация контроля при проектировании БИС
- Изоморфное вхождение и пересечение графов
локализация неисправности с помощью алгоритмов поиска МИПГ
покрытие схемы заданным набором типовых подсхем
- Автоморфизм графов
конструктивное перечисление структурных изомеров для
производных органических соединений
синтез тестов цифровых устройств
2.2. Нахождение кратчайших путей в графе
Начальные понятия
Будем рассматривать ориентированные графы G = <V , E > , дугам которых приписаны веса. Это означает, что каждой дуге <u , v > ÎE поставлено в соответствие некоторое вещественное число a (u , v ), называемое весом данной дуги.
Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s , t ÎV . Длину такого кратчайшего пути мы будем обозначать d (s , t ) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t , то полагаем d (s , t ) = ╔ . Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v 1 ,..., vp не будет повторов.
С другой стороны, если в графе существует контур отрицательной длины, то расстояние между некоторыми парами вершин становится неопределенным, потому что, обходя этот контур достаточное число раз, мы можем показать путь между этими вершинам