Главная » Учебно-методические материалы » ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ » Математические методы. Попова Н.В. |
22.12.2011, 14:29 | |
Нахождение минимального остова в графе Алгоритм решения
Продемонстрируем приведенный выше алгоритм на примере. Нахождение кратчайшего пути в графе Пусть дан граф, дугам которого приписаны веса. Задача о нахождении кратчайшего пути состоит в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины, при условии, что такой путь существует. Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам и каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем кратчайшие пути между городами. Вес дуги может соответствовать стоимости (или времени) передачи информации между вершинами. В этом случае мы ищем самый дешевый (или самый скорый). Данная задача может быть разбита на две:
Рассмотрим алгоритм решения для задачи первого типа: Необходимо найти путь от s - начальной вершины до t - конечной вершины. Каждой вершине присваиваем пометки I(Xi).
Как только все пометки расставлены, кратчайшие пути получают, используя состношение I(Xi') + c(Xi',Xi) = I(Xi) (1). Поясним работу данного алгоритма на примере. Для решения задачи второго типа можно применять данный алгоритм для каждой вершины. | http://matmetod-popova.narod.ru/ |