Оптимальные маршруты во взвешенных графах

Задача заключается в определении во взвешенном графе (псевдографе) G = (V, X, D) (например, на рис.2.4) маршрута от начальной вершины Vначдо конечной вершины Vкон, обладающего минимальной (максимальной) длиной.

Рис.2.4

Матрица весов D может быть представлена как обобщение матрицы смежности графа А, в котором при наличии ребра между вершинами Vi и Vj элемент dij (1 £ i, j £ n)равен не 1, как в А, а некоторому весу, присвоенному данному ребру. В практических приложениях под весом обычно понимают некоторое расстояние либо затраты на его преодоление. Для взвешенного графа на рис.2.4 матрица D имеет вид:

Рассмотрим основные алгоритмы, применяемые для решения данной задачи.

 








Дата добавления: 2015-10-05; просмотров: 1096;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.