Как алгоритм Дейкстры может применяться как к неориентированному, так и к направленному алгоритму в одной программе?

График представлен в следующем формате:

MAX 12
NODE 1 1
NODE 2 2 
NODE 3 3
NODE 4 4
NODE 5 5
NODE 6 6
NODE 7 7
NODE 9 9
NODE 8 8
NODE 10 10
NODE 11 11
NODE 12 12
EDGE 1 2
EDGE 2 3
EDGE 3 4
EDGE 4 5
EDGE 5 6
EDGE 6 7
EDGE 7 8
EDGE 8 9
EDGE 9 10
EDGE 10 11
EDGE 11 12
EDGE 1 12
EDGE 1 3
EDGE 1 4
EDGE 1 6
EDGE 1 8
EDGE 1 11
EDGE 1 10
EDGE 6 10
EDGE 3 6
EDGE 4 6
EDGE 5 7
EDGE 9 11

Мне нужно использовать соседний список для чтения этих краев. Но если я хочу использовать его как неориентированный граф, то есть игнорировать всю прямолинейность всех ребер. Как я мог узнать связность каждой пары узлов?

Например, кратчайшее расстояние между (УЗЕЛ 2, УЗЕЛ 8) равно 2 (2->1>8) в неориентированном графе, но с помощью алгоритма Дейкстры к этому графу получается 4 (2->3->6->7 ->8). Как я могу представить неориентированный граф, используя ту же технику для чтения ребер?


undirected-graph dijkstra adjacency-list
person NUO    schedule 23.04.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Если вы действительно не хотите менять технику чтения ребер, вам придется перебрать все остальные узлы, чтобы увидеть, находится ли ваш узел в их списке смежности, а не наоборот.

Это значительно увеличит время работы, но не сэкономит вам много памяти, поэтому я бы посоветовал просто изменить технику чтения по краям.

person Daan van der Kallen    schedule 23.04.2016
comment
Например, перейти на двойной список ссылок? То есть при чтении одного ребра два связанных узла добавят узел ссылки? - person NUO; 23.04.2016