Сумма ребер графа

@papillon83 · Регистрация: 22.02.2019

Студворк — интернет-сервис помощи студентам

Подскажите, как в этом коде сделать подсчет суммы ребер каждого пути
Например: из a в c мы идем путем a->b->c и сумма ребер будет равна 5

Python
1
2
3
4
5
6
7
8
9
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([
    ('a', 'b', 2), ('a', 'd', 4), ('b', 'c', 3), ('c', 'd', 1), 
    ('d', 'e', 6), ('d', 'f', 8), ('c', 'e', 6), ('e', 'h', 5), 
    ('e', 'g', 2), ('f', 'g', 12), ('g', 'h', 3)])
 
a=nx.all_simple_paths(G, 'a', 'c')
print(list(a))

@Catstail · 19.11.2020, 18:15

нет под рукой networkx. А что выдается на печать?

@papillon83 · 19.11.2020, 18:22 **[ТС]**

Catstail, [['a', 'b', 'c'], ['a', 'd', 'c'], ['a', 'd', 'e', 'c'], ['a', 'd', 'f', 'g', 'e', 'c'], ['a', 'd', 'f', 'g', 'h', 'e', 'c']] - все возможные пути из точки 'a' в точку 'c'
Нужно, чтобы после каждого пути выводилась еще и длина пути

@unfindable_404 · 19.11.2020, 19:24

Сообщение от papillon83

Нужно, чтобы после каждого пути выводилась еще и длина пути

Я, честно, не знаю такого штатного способа, но его не сложно дописать самому:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([
    ('a', 'b', 2), ('a', 'd', 4), ('b', 'c', 3), ('c', 'd', 1),
    ('d', 'e', 6), ('d', 'f', 8), ('c', 'e', 6), ('e', 'h', 5),
    ('e', 'g', 2), ('f', 'g', 12), ('g', 'h', 3)])
 
a = list(nx.all_simple_paths(G, 'a', 'c'))
 
 
# Функция возвращает вес пути, на вход принимает граф и путь в формате списка вершин
def get_weight_from_path(G, path_array):
    return sum(G.get_edge_data(path_array[i], path_array[i + 1])['weight']
               for i in range(len(path_array) - 1))
 
 
print([(i, get_weight_from_path(G, i)) for i in a])

Добавлено через 3 минуты
Ну а если вам нужен просто кратчайший путь, то его можно получить так:

Python
1
2
print(nx.dijkstra_path(G, source='a', target='c'),
      nx.dijkstra_path_length(G, source='a', target='c'))

@papillon83 · 19.11.2020, 19:59 **[ТС]**

unfindable_404, Благодарю

@papillon83 · 20.11.2020, 14:15 **[ТС]**

unfindable_404, Не подскажите еще кое-что, как вывести, кроме суммы длин ребер, длину каждого ребра
например (a , b [Длина ребра] b,c [Длина ребра],[Сумма длин ребер])

@unfindable_404 · 20.11.2020, 15:10

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from pprint import pprint
import networkx as nx
 
 
G = nx.Graph()
G.add_weighted_edges_from([
    ('a', 'b', 2), ('a', 'd', 4), ('b', 'c', 3), ('c', 'd', 1),
    ('d', 'e', 6), ('d', 'f', 8), ('c', 'e', 6), ('e', 'h', 5),
    ('e', 'g', 2), ('f', 'g', 12), ('g', 'h', 3)])
 
a = list(nx.all_simple_paths(G, 'a', 'c'))
 
 
def get_weight_from_path(G, path_array):
    return sum(G.get_edge_data(path_array[i], path_array[i + 1])['weight']
               for i in range(len(path_array) - 1))
 
 
def get_weights_from_path_with_edges_weight(G, path_array):
    itog = []
    for i in range(len(path_array) - 1):
        tmp = [(path_array[i], path_array[i + 1])]
        tmp.append(G.get_edge_data(
            path_array[i], path_array[i + 1])['weight'])
        itog.append(tmp)
 
    itog.append(sum(G.get_edge_data(path_array[i],
                                    path_array[i + 1])['weight']
                for i in range(len(path_array) - 1)))
 
    return itog
 
 
#print([(i, get_weight_from_path(G, i)) for i in a])
pprint([(get_weights_from_path_with_edges_weight(G, i)) for i in a])

Так?

@papillon83 · 20.11.2020, 15:14 **[ТС]**

unfindable_404, Вроде так, большое спасибо

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@Catstail Супер-модератор 38195 / 21128 / 4309 Регистрация: 12.02.2012 Сообщений: 34,733 Записей в блоге: 14
	19.11.2020, 18:15
	нет под рукой networkx. А что выдается на печать? 0

@papillon83 0 / 0 / 0 Регистрация: 22.02.2019 Сообщений: 112
	19.11.2020, 18:22 [ТС]
	Catstail, [['a', 'b', 'c'], ['a', 'd', 'c'], ['a', 'd', 'e', 'c'], ['a', 'd', 'f', 'g', 'e', 'c'], ['a', 'd', 'f', 'g', 'h', 'e', 'c']] - все возможные пути из точки 'a' в точку 'c' Нужно, чтобы после каждого пути выводилась еще и длина пути 0

@papillon83 0 / 0 / 0 Регистрация: 22.02.2019 Сообщений: 112
	19.11.2020, 19:59 [ТС]
	unfindable_404, Благодарю 0

@papillon83 0 / 0 / 0 Регистрация: 22.02.2019 Сообщений: 112
	20.11.2020, 14:15 [ТС]
	unfindable_404, Не подскажите еще кое-что, как вывести, кроме суммы длин ребер, длину каждого ребра например (a , b [Длина ребра] b,c [Длина ребра],[Сумма длин ребер]) 0

@papillon83 0 / 0 / 0 Регистрация: 22.02.2019 Сообщений: 112
	20.11.2020, 15:14 [ТС]
	unfindable_404, Вроде так, большое спасибо 0

Опции темы

Сумма ребер графа

Решение

Решение