Найти кратчайший путь к одному из множества узлов с атрибутом
У меня есть граф networkx, представляющий минимальное связующее дерево из примерно 1 миллиона объектов (вершин). Мне интересно, есть ли эффективный способ найти кратчайший путь между данной вершиной и одной из многих других вершин.
Вот пример графа с меньшим числом вершин (110)
nodes = [(0.0, {'label': 2}) ,
(1.0, {'label': 2}) ,
(2.0, {'label': 0}) ,
(3.0, {'label': 2}) ,
(4.0, {'label': 2}) ,
(5.0, {'label': 0}) ,
(6.0, {'label': 0}) ,
(7.0, {'label': 2}) ,
(8.0, {'label': 2}) ,
(9.0, {'label': 1}) ,
(10.0, {'label': 0}) ,
(11.0, {'label': 1}) ,
(12.0, {'label': 1}) ,
(13.0, {'label': 0}) ,
(14.0, {'label': 1}) ,
(15.0, {'label': 2}) ,
(16.0, {'label': 1}) ,
(17.0, {'label': 1}) ,
(18.0, {'label': 2}) ,
(19.0, {'label': 2}) ,
(20.0, {'label': 0}) ,
(21.0, {'label': 1}) ,
(22.0, {'label': 1}) ,
(23.0, {'label': 0}) ,
(24.0, {'label': 1}) ,
(25.0, {'label': 2}) ,
(26.0, {'label': 0}) ,
(27.0, {'label': 0}) ,
(28.0, {'label': 1}) ,
(29.0, {'label': 0}) ,
(30.0, {'label': 2}) ,
(31.0, {'label': 1}) ,
(32.0, {'label': 2}) ,
(33.0, {'label': 1}) ,
(34.0, {'label': 1}) ,
(35.0, {'label': 1}) ,
(36.0, {'label': 1}) ,
(37.0, {'label': 2}) ,
(38.0, {'label': 0}) ,
(39.0, {'label': 0}) ,
(40.0, {'label': 2}) ,
(41.0, {'label': 0}) ,
(42.0, {'label': 1}) ,
(43.0, {'label': 0}) ,
(44.0, {'label': 0}) ,
(45.0, {'label': 2}) ,
(46.0, {'label': 0}) ,
(47.0, {'label': 2}) ,
(48.0, {'label': 0}) ,
(49.0, {'label': 1}) ,
(50.0, {'label': 0}) ,
(51.0, {'label': 1}) ,
(52.0, {'label': 2}) ,
(53.0, {'label': 0}) ,
(54.0, {'label': 1}) ,
(55.0, {'label': 1}) ,
(56.0, {'label': 2}) ,
(57.0, {'label': 1}) ,
(58.0, {'label': 1}) ,
(59.0, {'label': 0}) ,
(60.0, {'label': 2}) ,
(61.0, {'label': 1}) ,
(62.0, {'label': 1}) ,
(63.0, {'label': 2}) ,
(64.0, {'label': 0}) ,
(65.0, {'label': 0}) ,
(66.0, {'label': 0}) ,
(67.0, {'label': 0}) ,
(68.0, {'label': 1}) ,
(69.0, {'label': 2}) ,
(70.0, {'label': 0}) ,
(71.0, {'label': 1}) ,
(72.0, {'label': 0}) ,
(73.0, {'label': 2}) ,
(74.0, {'label': 0}) ,
(75.0, {'label': 1}) ,
(76.0, {'label': 1}) ,
(77.0, {'label': 0}) ,
(78.0, {'label': 2}) ,
(79.0, {'label': 2}) ,
(80.0, {'label': 2}) ,
(81.0, {'label': 1}) ,
(82.0, {'label': 2}) ,
(83.0, {'label': 2}) ,
(84.0, {'label': 1}) ,
(85.0, {'label': 0}) ,
(86.0, {'label': 1}) ,
(87.0, {'label': 2}) ,
(88.0, {'label': 1}) ,
(89.0, {'label': 0}) ,
(90.0, {'label': 0}) ,
(91.0, {'label': 2}) ,
(92.0, {'label': 0}) ,
(93.0, {'label': 1}) ,
(94.0, {'label': 1}) ,
(95.0, {'label': 2}) ,
(96.0, {'label': 2}) ,
(97.0, {'label': 0}) ,
(98.0, {'label': 2}) ,
(99.0, {'label': 2}) ,
(100.0, {'label': -1}) ,
(101.0, {'label': -1}) ,
(102.0, {'label': 1}) ,
(103.0, {'label': -1}) ,
(104.0, {'label': -1}) ,
(105.0, {'label': -1}) ,
(106.0, {'label': -1}) ,
(107.0, {'label': 1}) ,
(108.0, {'label': 0}) ,
(109.0, {'label': -1})]
edges = [(0.0, 25.0, {'weight': 1.3788141613435239}) ,
(0.0, 15.0, {'weight': 1.1948288781935414}) ,
(1.0, 99.0, {'weight': 2.1024875417678257}) ,
(1.0, 52.0, {'weight': 1.5298566582843918}) ,
(2.0, 59.0, {'weight': 1.2222170767316791}) ,
(3.0, 96.0, {'weight': 0.77235026806254947}) ,
(3.0, 98.0, {'weight': 0.75540026318653475}) ,
(3.0, 83.0, {'weight': 0.63745598060956865}) ,
(4.0, 8.0, {'weight': 1.1460983565815646}) ,
(5.0, 39.0, {'weight': 0.57882005244148982}) ,
(6.0, 27.0, {'weight': 0.77903808587705414}) ,
(6.0, 38.0, {'weight': 0.87763345274858739}) ,
(7.0, 83.0, {'weight': 1.0592473391743824}) ,
(7.0, 52.0, {'weight': 1.1650063193499598}) ,
(8.0, 18.0, {'weight': 0.62985157194068553}) ,
(8.0, 63.0, {'weight': 0.66061808561292024}) ,
(9.0, 57.0, {'weight': 0.73138423240527128}) ,
(9.0, 14.0, {'weight': 0.68690071596776681}) ,
(10.0, 43.0, {'weight': 1.0938913337235003}) ,
(11.0, 76.0, {'weight': 1.8066534138474315}) ,
(11.0, 22.0, {'weight': 1.5814274601380762}) ,
(12.0, 68.0, {'weight': 0.82964162447510292}) ,
(12.0, 28.0, {'weight': 0.56687613489965616}) ,
(13.0, 41.0, {'weight': 0.67883257822079479}) ,
(13.0, 70.0, {'weight': 0.69594526555853065}) ,
(13.0, 39.0, {'weight': 0.62690609201673064}) ,
(14.0, 42.0, {'weight': 0.51384098628821639}) ,
(15.0, 91.0, {'weight': 0.80363040334950342}) ,
(15.0, 63.0, {'weight': 0.74055429404201112}) ,
(16.0, 75.0, {'weight': 0.89225782872169068}) ,
(16.0, 36.0, {'weight': 0.97796463842832249}) ,
(16.0, 61.0, {'weight': 1.2426060084547763}) ,
(17.0, 24.0, {'weight': 0.48569989925661516}) ,
(17.0, 88.0, {'weight': 0.58411688395739225}) ,
(17.0, 42.0, {'weight': 0.48569989925661516}) ,
(18.0, 19.0, {'weight': 0.73750301595928458}) ,
(18.0, 87.0, {'weight': 0.62985157194068553}) ,
(19.0, 80.0, {'weight': 0.77740196142918039}) ,
(20.0, 53.0, {'weight': 1.5817584651620507}) ,
(21.0, 33.0, {'weight': 1.558483049272277}) ,
(21.0, 35.0, {'weight': 1.022218339608882}) ,
(22.0, 93.0, {'weight': 1.4628634684132413}) ,
(22.0, 101.0, {'weight': 7.494583622053641}) ,
(23.0, 97.0, {'weight': 0.86085201141197409}) ,
(23.0, 90.0, {'weight': 1.4629842172999594}) ,
(23.0, 65.0, {'weight': 0.94746570241498318}) ,
(24.0, 34.0, {'weight': 0.55323853417352553}) ,
(25.0, 104.0, {'weight': 4.9839694794161371}) ,
(26.0, 85.0, {'weight': 1.5024751933287497}) ,
(26.0, 46.0, {'weight': 1.2053565344116006}) ,
(27.0, 72.0, {'weight': 0.72860577250944303}) ,
(27.0, 92.0, {'weight': 0.74002007166874428}) ,
(28.0, 54.0, {'weight': 0.55323853417352553}) ,
(29.0, 50.0, {'weight': 0.81426784351619774}) ,
(30.0, 98.0, {'weight': 0.77235026806254947}) ,
(30.0, 78.0, {'weight': 0.79413937142096647}) ,
(30.0, 95.0, {'weight': 0.78901093530213129}) ,
(31.0, 68.0, {'weight': 0.98851671776185412}) ,
(32.0, 95.0, {'weight': 0.8579399666494596}) ,
(34.0, 54.0, {'weight': 0.55323853417352553}) ,
(34.0, 55.0, {'weight': 0.60906522381767525}) ,
(35.0, 62.0, {'weight': 0.66697239833732958}) ,
(36.0, 93.0, {'weight': 1.2932994772208264}) ,
(37.0, 80.0, {'weight': 0.85527462610640648}) ,
(37.0, 96.0, {'weight': 0.85527462610640648}) ,
(38.0, 46.0, {'weight': 0.95334944284759993}) ,
(39.0, 50.0, {'weight': 0.52028039541706872}) ,
(40.0, 69.0, {'weight': 1.7931323073700682}) ,
(42.0, 62.0, {'weight': 0.51384098628821639}) ,
(42.0, 81.0, {'weight': 0.5466147583189902}) ,
(43.0, 65.0, {'weight': 1.0581157274507453}) ,
(44.0, 108.0, {'weight': 3.0598509599260266}) ,
(44.0, 70.0, {'weight': 1.0805691635112824}) ,
(45.0, 56.0, {'weight': 1.3420236519319457}) ,
(45.0, 79.0, {'weight': 1.6201017824952586}) ,
(46.0, 53.0, {'weight': 1.070516213146298}) ,
(47.0, 78.0, {'weight': 1.2822937333699174}) ,
(47.0, 103.0, {'weight': 3.9053251231648707}) ,
(48.0, 97.0, {'weight': 0.86085201141197409}) ,
(48.0, 67.0, {'weight': 0.75656062694199944}) ,
(49.0, 94.0, {'weight': 1.6216528905308547}) ,
(49.0, 86.0, {'weight': 0.80157999082131093}) ,
(49.0, 62.0, {'weight': 0.7081136236724922}) ,
(51.0, 102.0, {'weight': 1.4704389417937378}) ,
(51.0, 71.0, {'weight': 0.83506431983724716}) ,
(54.0, 75.0, {'weight': 0.70074754481170742}) ,
(55.0, 58.0, {'weight': 0.78571631647476448}) ,
(56.0, 82.0, {'weight': 1.3387438494166808}) ,
(57.0, 84.0, {'weight': 1.558483049272277}) ,
(59.0, 64.0, {'weight': 1.0416266944398496}) ,
(60.0, 98.0, {'weight': 1.2534403896544031}) ,
(63.0, 73.0, {'weight': 0.83646303763566465}) ,
(64.0, 72.0, {'weight': 0.8620326535711742}) ,
(66.0, 77.0, {'weight': 0.79981721989351606}) ,
(67.0, 72.0, {'weight': 0.74002007166874428}) ,
(69.0, 83.0, {'weight': 1.5000235782351021}) ,
(70.0, 77.0, {'weight': 0.75999034076724692}) ,
(71.0, 88.0, {'weight': 0.66450874893016454}) ,
(74.0, 97.0, {'weight': 0.8743417572549379}) ,
(76.0, 107.0, {'weight': 2.0300278349030831}) ,
(77.0, 89.0, {'weight': 0.75999034076724692}) ,
(79.0, 106.0, {'weight': 4.5661761296968333}) ,
(82.0, 95.0, {'weight': 1.083633962514291}) ,
(84.0, 99.0, {'weight': 2.1024875417678257}) ,
(89.0, 92.0, {'weight': 0.75419548272456249}) ,
(100.0, 107.0, {'weight': 2.9259491743365307}) ,
(101.0, 109.0, {'weight': 7.6747981730730297}) ,
(102.0, 108.0, {'weight': 4.3128725576385092}) ,
(104.0, 105.0, {'weight': 7.5515191839631273})]
G2 = nx.Graph()
G2.add_nodes_from(nodes)
G2.add_edges_from(edges)
Я хочу, чтобы "какая вершина, имеющая метку >= 0, была ближе к каждой из вершин с меткой = -1". С небольшим графом, подобным этому, подход грубой силы с использованием что-то вроде nx.all_pairs_dijkstra_path_length(), а затем проверка меток работает нормально, но она не масштабируется до очень больших графиков. Существуют ли более эффективные алгоритмы, особенно если они встроены в networkx, которые я мог бы использовать?
Обновление:
Я использовал превосходное предложение Ричарда и комментарий ниже, чтобы написать это. Что мне на самом деле нужно, так это множество ярлыков, которые, я думаю, сделали вещи менее грязными, чем Ричард упоминал в networkx. Вся повторная маркировка заняла 45 секунд на наборе данных, что заняло час. грубой силой!def relabel(G, indices_to_relabel):
"""
Update the anomaly labels to be the closest cluster.
"""
# Add a "special" node that has zero weight to all the cluster nodes
print('Adding special node')
G.add_node('special', {'label': 'special'})
special_edges = [(n, 'special', {'weight': 0})
for n, ndat in G.nodes_iter(data=True)
if ndat['label'] != 'special' and ndat['label'] >= 0]
G.add_edges_from(special_edges)
print('Calculating path from special node to all other nodes')
paths = nx.shortest_path(G, source='special', target=None, weight='weight')
print('Updating labels')
new_labels = np.array([ndat['label'] for _, ndat in G.nodes_iter(data=True)])
new_labels[indices_to_relabel] = [G.node[paths[n][1]]['label'] for n in indices_to_relabel]
# Clean up
G.remove_node('special')
return new_labels
3 ответа:
Я не думаю, что есть такой алгоритм, встроенный в networkx, но кажется, что было бы разумно иметь алгоритм, который расширяет наименее затратный путь, пока не будет достигнуто условие. Однако, несмотря на то, что networkx не включает в себя такую возможность, довольно легко построить алгоритм для этого.
- вызовите узлы с
label==-1исходными узлами.- назовите узел с
label>=0, который находится ближе всего к исходному узлу, его целевым узлом. Наша цель-найти цель. узлы.- Создайте новый узел. Это будет специальный узел .
- соедините все потенциальные целевые узлы со специальным узлом с ребрами веса 0.
- для каждого исходного узла найдите кратчайший путь к специальному узлу. Предпоследний узел на этом пути обязательно является целевым узлом и является ближайшим к исходному узлу.
- Когда закончите, удалите специальный узел и все его соединительные кромки.
Если число исходных узлов равно S , этот алгоритм выполняется в O(S(|E|+|V| log |V|)) времени (предполагая, что алгоритм кратчайшего пути-это Дейкстра).
(Возможно, я неправильно понял, хотите ли вы, чтобы -1 был ближе к >=0 или >=0 был ближе к -1. Если у меня есть, просто инвертируйте маркировку источника/цели.)
#!/usr/bin/env python3 import networkx as nx nodes = [(0.0, {'label': 2}) , (1.0, {'label': 2}) , (2.0, {'label': 0}) , (3.0, {'label': 2}) , (4.0, {'label': 2}) , (5.0, {'label': 0}) , (6.0, {'label': 0}) , (7.0, {'label': 2}) , (8.0, {'label': 2}) , (9.0, {'label': 1}) , (10.0, {'label': 0}) , (11.0, {'label': 1}) , (12.0, {'label': 1}) , (13.0, {'label': 0}) , (14.0, {'label': 1}) , (15.0, {'label': 2}) , (16.0, {'label': 1}) , (17.0, {'label': 1}) , (18.0, {'label': 2}) , (19.0, {'label': 2}) , (20.0, {'label': 0}) , (21.0, {'label': 1}) , (22.0, {'label': 1}) , (23.0, {'label': 0}) , (24.0, {'label': 1}) , (25.0, {'label': 2}) , (26.0, {'label': 0}) , (27.0, {'label': 0}) , (28.0, {'label': 1}) , (29.0, {'label': 0}) , (30.0, {'label': 2}) , (31.0, {'label': 1}) , (32.0, {'label': 2}) , (33.0, {'label': 1}) , (34.0, {'label': 1}) , (35.0, {'label': 1}) , (36.0, {'label': 1}) , (37.0, {'label': 2}) , (38.0, {'label': 0}) , (39.0, {'label': 0}) , (40.0, {'label': 2}) , (41.0, {'label': 0}) , (42.0, {'label': 1}) , (43.0, {'label': 0}) , (44.0, {'label': 0}) , (45.0, {'label': 2}) , (46.0, {'label': 0}) , (47.0, {'label': 2}) , (48.0, {'label': 0}) , (49.0, {'label': 1}) , (50.0, {'label': 0}) , (51.0, {'label': 1}) , (52.0, {'label': 2}) , (53.0, {'label': 0}) , (54.0, {'label': 1}) , (55.0, {'label': 1}) , (56.0, {'label': 2}) , (57.0, {'label': 1}) , (58.0, {'label': 1}) , (59.0, {'label': 0}) , (60.0, {'label': 2}) , (61.0, {'label': 1}) , (62.0, {'label': 1}) , (63.0, {'label': 2}) , (64.0, {'label': 0}) , (65.0, {'label': 0}) , (66.0, {'label': 0}) , (67.0, {'label': 0}) , (68.0, {'label': 1}) , (69.0, {'label': 2}) , (70.0, {'label': 0}) , (71.0, {'label': 1}) , (72.0, {'label': 0}) , (73.0, {'label': 2}) , (74.0, {'label': 0}) , (75.0, {'label': 1}) , (76.0, {'label': 1}) , (77.0, {'label': 0}) , (78.0, {'label': 2}) , (79.0, {'label': 2}) , (80.0, {'label': 2}) , (81.0, {'label': 1}) , (82.0, {'label': 2}) , (83.0, {'label': 2}) , (84.0, {'label': 1}) , (85.0, {'label': 0}) , (86.0, {'label': 1}) , (87.0, {'label': 2}) , (88.0, {'label': 1}) , (89.0, {'label': 0}) , (90.0, {'label': 0}) , (91.0, {'label': 2}) , (92.0, {'label': 0}) , (93.0, {'label': 1}) , (94.0, {'label': 1}) , (95.0, {'label': 2}) , (96.0, {'label': 2}) , (97.0, {'label': 0}) , (98.0, {'label': 2}) , (99.0, {'label': 2}) , (100.0, {'label': -1}) , (101.0, {'label': -1}) , (102.0, {'label': 1}) , (103.0, {'label': -1}) , (104.0, {'label': -1}) , (105.0, {'label': -1}) , (106.0, {'label': -1}) , (107.0, {'label': 1}) , (108.0, {'label': 0}) , (109.0, {'label': -1})] edges = [(0.0, 25.0, {'weight': 1.3788141613435239}) , (0.0, 15.0, {'weight': 1.1948288781935414}) , (1.0, 99.0, {'weight': 2.1024875417678257}) , (1.0, 52.0, {'weight': 1.5298566582843918}) , (2.0, 59.0, {'weight': 1.2222170767316791}) , (3.0, 96.0, {'weight': 0.77235026806254947}) , (3.0, 98.0, {'weight': 0.75540026318653475}) , (3.0, 83.0, {'weight': 0.63745598060956865}) , (4.0, 8.0, {'weight': 1.1460983565815646}) , (5.0, 39.0, {'weight': 0.57882005244148982}) , (6.0, 27.0, {'weight': 0.77903808587705414}) , (6.0, 38.0, {'weight': 0.87763345274858739}) , (7.0, 83.0, {'weight': 1.0592473391743824}) , (7.0, 52.0, {'weight': 1.1650063193499598}) , (8.0, 18.0, {'weight': 0.62985157194068553}) , (8.0, 63.0, {'weight': 0.66061808561292024}) , (9.0, 57.0, {'weight': 0.73138423240527128}) , (9.0, 14.0, {'weight': 0.68690071596776681}) , (10.0, 43.0, {'weight': 1.0938913337235003}) , (11.0, 76.0, {'weight': 1.8066534138474315}) , (11.0, 22.0, {'weight': 1.5814274601380762}) , (12.0, 68.0, {'weight': 0.82964162447510292}) , (12.0, 28.0, {'weight': 0.56687613489965616}) , (13.0, 41.0, {'weight': 0.67883257822079479}) , (13.0, 70.0, {'weight': 0.69594526555853065}) , (13.0, 39.0, {'weight': 0.62690609201673064}) , (14.0, 42.0, {'weight': 0.51384098628821639}) , (15.0, 91.0, {'weight': 0.80363040334950342}) , (15.0, 63.0, {'weight': 0.74055429404201112}) , (16.0, 75.0, {'weight': 0.89225782872169068}) , (16.0, 36.0, {'weight': 0.97796463842832249}) , (16.0, 61.0, {'weight': 1.2426060084547763}) , (17.0, 24.0, {'weight': 0.48569989925661516}) , (17.0, 88.0, {'weight': 0.58411688395739225}) , (17.0, 42.0, {'weight': 0.48569989925661516}) , (18.0, 19.0, {'weight': 0.73750301595928458}) , (18.0, 87.0, {'weight': 0.62985157194068553}) , (19.0, 80.0, {'weight': 0.77740196142918039}) , (20.0, 53.0, {'weight': 1.5817584651620507}) , (21.0, 33.0, {'weight': 1.558483049272277}) , (21.0, 35.0, {'weight': 1.022218339608882}) , (22.0, 93.0, {'weight': 1.4628634684132413}) , (22.0, 101.0, {'weight': 7.494583622053641}) , (23.0, 97.0, {'weight': 0.86085201141197409}) , (23.0, 90.0, {'weight': 1.4629842172999594}) , (23.0, 65.0, {'weight': 0.94746570241498318}) , (24.0, 34.0, {'weight': 0.55323853417352553}) , (25.0, 104.0, {'weight': 4.9839694794161371}) , (26.0, 85.0, {'weight': 1.5024751933287497}) , (26.0, 46.0, {'weight': 1.2053565344116006}) , (27.0, 72.0, {'weight': 0.72860577250944303}) , (27.0, 92.0, {'weight': 0.74002007166874428}) , (28.0, 54.0, {'weight': 0.55323853417352553}) , (29.0, 50.0, {'weight': 0.81426784351619774}) , (30.0, 98.0, {'weight': 0.77235026806254947}) , (30.0, 78.0, {'weight': 0.79413937142096647}) , (30.0, 95.0, {'weight': 0.78901093530213129}) , (31.0, 68.0, {'weight': 0.98851671776185412}) , (32.0, 95.0, {'weight': 0.8579399666494596}) , (34.0, 54.0, {'weight': 0.55323853417352553}) , (34.0, 55.0, {'weight': 0.60906522381767525}) , (35.0, 62.0, {'weight': 0.66697239833732958}) , (36.0, 93.0, {'weight': 1.2932994772208264}) , (37.0, 80.0, {'weight': 0.85527462610640648}) , (37.0, 96.0, {'weight': 0.85527462610640648}) , (38.0, 46.0, {'weight': 0.95334944284759993}) , (39.0, 50.0, {'weight': 0.52028039541706872}) , (40.0, 69.0, {'weight': 1.7931323073700682}) , (42.0, 62.0, {'weight': 0.51384098628821639}) , (42.0, 81.0, {'weight': 0.5466147583189902}) , (43.0, 65.0, {'weight': 1.0581157274507453}) , (44.0, 108.0, {'weight': 3.0598509599260266}) , (44.0, 70.0, {'weight': 1.0805691635112824}) , (45.0, 56.0, {'weight': 1.3420236519319457}) , (45.0, 79.0, {'weight': 1.6201017824952586}) , (46.0, 53.0, {'weight': 1.070516213146298}) , (47.0, 78.0, {'weight': 1.2822937333699174}) , (47.0, 103.0, {'weight': 3.9053251231648707}) , (48.0, 97.0, {'weight': 0.86085201141197409}) , (48.0, 67.0, {'weight': 0.75656062694199944}) , (49.0, 94.0, {'weight': 1.6216528905308547}) , (49.0, 86.0, {'weight': 0.80157999082131093}) , (49.0, 62.0, {'weight': 0.7081136236724922}) , (51.0, 102.0, {'weight': 1.4704389417937378}) , (51.0, 71.0, {'weight': 0.83506431983724716}) , (54.0, 75.0, {'weight': 0.70074754481170742}) , (55.0, 58.0, {'weight': 0.78571631647476448}) , (56.0, 82.0, {'weight': 1.3387438494166808}) , (57.0, 84.0, {'weight': 1.558483049272277}) , (59.0, 64.0, {'weight': 1.0416266944398496}) , (60.0, 98.0, {'weight': 1.2534403896544031}) , (63.0, 73.0, {'weight': 0.83646303763566465}) , (64.0, 72.0, {'weight': 0.8620326535711742}) , (66.0, 77.0, {'weight': 0.79981721989351606}) , (67.0, 72.0, {'weight': 0.74002007166874428}) , (69.0, 83.0, {'weight': 1.5000235782351021}) , (70.0, 77.0, {'weight': 0.75999034076724692}) , (71.0, 88.0, {'weight': 0.66450874893016454}) , (74.0, 97.0, {'weight': 0.8743417572549379}) , (76.0, 107.0, {'weight': 2.0300278349030831}) , (77.0, 89.0, {'weight': 0.75999034076724692}) , (79.0, 106.0, {'weight': 4.5661761296968333}) , (82.0, 95.0, {'weight': 1.083633962514291}) , (84.0, 99.0, {'weight': 2.1024875417678257}) , (89.0, 92.0, {'weight': 0.75419548272456249}) , (100.0, 107.0, {'weight': 2.9259491743365307}) , (101.0, 109.0, {'weight': 7.6747981730730297}) , (102.0, 108.0, {'weight': 4.3128725576385092}) , (104.0, 105.0, {'weight': 7.5515191839631273})] G2 = nx.Graph() G2.add_nodes_from(nodes) G2.add_edges_from(edges) G2.add_node('special', {'label': 'special'}) special_edges = [] for n, ndat in G2.nodes_iter(data=True): if ndat['label']!='special' and ndat['label']>=0: special_edges.append( (n,'special', {'weight':0}) ) G2.add_edges_from(special_edges) for n, ndat in G2.nodes_iter(data=True): if ndat['label']==-1: path = nx.shortest_path(G2, source=n, target='special', weight='weight') ndat['closest'] = path[-2] #Closest node with label>=0 G2.remove_node('special')
Если я понимаю вашу проблему, то у вас есть проблема коммивояжера, что означает, что нет точного решения быстрее, чем (в худшем случае) тестирование когда-либо одной возможности.
h = heapq solution = {} g = build_nx_graph() for node in g: if label_is_neg_1(node): solution[node] = false heappush(h, (0, node)) while h: distance, node = heappop(h) for neighbour, neighbour_dist in iterate_neighbours(g): bs = best_solution(neighbour, neighbour_dist) if not bs == solution.get(neighbour, bs): solution[neighbour] = bs heappush(h, (bs, neighbour)) if len(solution) == len(g): breakЭтот неполный псевдокод должен начинаться на всех узлах -1 и" разветвляться", вычисляя расстояние до всех не -1 узлов по порядку.