Speaker
Гурами Шалвович Цициашвили
(ИПМ ДВО РАН)
Description
Решается задача определения кратчайших путей в конечном взвешенном орграфе из стартовой вершины в остальные вершины графа. Эта задача решается введением списков меток в алгоритм Дейкстра. С помощью этой процедуры также подсчитывается число кратчайших путей из стартовой вершины во все вершины графа. Эта величина характеризует надежность кратчайших путей в графе. Данная процедура может быть использована как для невзвешенного графа, так и для планарного графа. В случае планарного графа определяются кратчайшие пути из граней планарного графа во внешнюю грань. Здесь длиной пути полагается число границ между гранями, которые пересекает путь из грани во внешнюю грань.
| Секция конференции | Информационные и вычислительные системы |
|---|
Primary author
Гурами Шалвович Цициашвили
(ИПМ ДВО РАН)
