Учитывая матрицу смежности для невзвешенного неориентированного графа, существует ли эффективный способ (полиномиальный алгоритм) расширить / увеличить длину кратчайшего пути между любыми заданными двумя узлами s и t?
Пример:
В приведенном ниже примере есть 5 различных «кратчайших путей» от вершины s = 1 до вершины t = 5, каждый из которых имеет длину 3. Я хочу удалить наименьшее количество ребер, чтобы длина кратчайшего пути была равна 4 или более. (Отключение графика - нормально.)
Матрица смежности (расширена для исправления примера):
0 1 0 0 0 1 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0 1
0 1 0 0 1 1 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0
1 0 0 1 1 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 1 0 0 0
1 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
представляющий этот график:
Минимальные затраты на увеличение длины кратчайшего пути с 3 до 4 - это удаление двух кромок (1,2) и (5,9).
Цель:
Можете ли вы дать какие-либо идеи для общего алгоритма, который находит набор ребер, которые необходимо удалить в общем случае?
Исправление: Как отмечалось в моих комментариях, этот пример не является полным. Добавив еще две вершины 10 и 11 (показаны красным), пример спасен.