使用python创建带有权重的路径图
使用Python创建带有权重的路径图可以通过使用图论库NetworkX来实现。下面是一个完善且全面的答案：
创建带有权重的路径图是指在图中的每条边上赋予一个权重值，表示从一个节点到另一个节点的距离或成本。这样的路径图在很多实际应用中非常有用，例如路由算法、最短路径问题、社交网络分析等。
在Python中，可以使用NetworkX库来创建带有权重的路径图。NetworkX是一个强大的图论库，提供了丰富的图操作和算法。下面是使用NetworkX创建带有权重的路径图的步骤：
- 安装NetworkX库：
- 安装NetworkX库：
- 导入NetworkX库：
- 导入NetworkX库：
- 创建一个空的有向图：
- 创建一个空的有向图：
- 添加带有权重的边：
- 添加带有权重的边：
- 访问边的权重：
- 访问边的权重：
- 使用NetworkX提供的算法进行路径计算：
- 使用NetworkX提供的算法进行路径计算：
在上述代码中，我们首先创建了一个有向图对象G，然后使用add_edge方法添加了带有权重的边。可以通过访问G的边属性来获取边的权重值。最后，我们使用nx.shortest_path算法计算了从节点'A'到节点'D'的最短路径，其中weight参数指定了权重属性的名称。
推荐的腾讯云相关产品是腾讯云图数据库TGraph，它是一种高性能、高可用、分布式的图数据库产品，适用于存储和处理大规模图数据。TGraph提供了灵活的图存储和图计算能力，可以方便地进行路径查询、社交网络分析、推荐系统等应用场景。
腾讯云TGraph产品介绍链接地址：https://cloud.tencent.com/product/tgraph
注意：本答案仅提供了一个示例，实际应用中可能需要根据具体需求进行适当的调整和扩展。
相关·内容
我已经用python编写了Prim的算法，但这是一个带有节点和边的加权图作为输入，这不是我所拥有的。
我如何将给定的坐标转换为图形，以便程序可以接受输入，并获得有意义的答案？
浏览 0提问于2017-10-17得票数 0
1回答
我有一个有向图，有彩色的边(红和蓝)，可能包含循环。问题是编写一个给定两个顶点(s，t)的算法，该算法在s和t之间找到具有最小颜色变化的路径(如果存在这样的路径)。
我找到了一个使用Dijkstra变体的解决方案(我创建了一个新的图，其中每个顶点对应于上一个图的边，并包含边的颜色。例如:如果(1,2)是旧图中的边，那么(1/2)是新图中的一个顶点。我连接了“相邻边”顶点，而新图中改变颜色的边的权重为1，其中相同的颜色转换为0)。
我在寻找线性时间(V和E)的解。上面的图在新图中使用了VxE边。
有这样的解决方案来找到最小路径吗？
浏览 1提问于2017-04-16得票数 1
回答已采纳
1回答
我有下面的图，其中每个顶点都有一个关联的“概率”()。
我想要找到从节点0到最后一个节点的路径(这里是最高的索引，这里是5)，它具有最大的乘概率。在这个图中，最佳路径是0-1-4-5，这给出了0.72的概率.
我考虑过使用BFS来找到起始节点和结束节点之间的所有路径，然后将每个节点的概率乘以，但我认为这对于所有的图来说都是一种可行的方法。我如何使用python来解决这个问题？
浏览 4提问于2015-10-22得票数 0
回答已采纳
4回答
我正在实现一个由100,000+节点组成的巨大的有向图。我刚开始学习python，所以我只知道这两种搜索算法。如果我想找到任意两个节点之间的最短距离，哪一个会更有效？有没有其他我不知道的更好的方法？
谢谢您抽时间见我
浏览 0提问于2013-05-23得票数 0
回答已采纳
我有一个有向无环图(DAG)，每个节点都有一个相关的权重。我想找出前'n‘个(例如5个)权重最大的路径，其中路径的权重定义为其节点的所有权重的总和。我如何才能做到这一点呢？
准确性是可取的，但可以牺牲性能。潜在地，图可以具有10,000+节点和/或边。
编辑:权重将是大于或等于零的数字。
浏览 0提问于2012-11-06得票数 2
回答已采纳
我想构造一个无向加权图(作为python dict)，其中权重是由Mapdata.csv文件中给出的边连接的两个节点之间的欧几里得距离。我在谷歌上找不到任何东西。请帮帮我。我想要创建加权无向图的python代码。
为了在文件中表示图，我们列出了顶点和边的数量，然后列出了顶点(索引，后面是它的x和y坐标)，然后列出了边(顶点对)。例如，下图显示了一个图形及其文件表示：
浏览 2提问于2019-07-17得票数 0
2回答
我知道贝尔曼-福特算法适用于有向图。它是否适用于无向图？似乎对于无向图，它将无法检测循环，因为并行边将被视为循环。这是不是真的？该算法可以应用吗？
浏览 1提问于2013-02-09得票数 21
回答已采纳
1回答
我正在使用Python 3和Networkx1.11。
我制作了一个加权图，在边和一些节点上有权重，但是当我计算最短路径的权重时，没有考虑节点的权重(下面的代码)。
有人知道如何确保节点权重被考虑吗？
谢谢!相同的
import networkx as nx
from matplotlib import pyplot as plt
# Set up a station map
all_stations = ['a','b','c','d','e']
interchange_stations = ['b&
浏览 0提问于2018-03-06得票数 1
回答已采纳
我正在尝试解决一个复杂的问题，我相信这个问题可以简化为解决如下所示的加权无向图。这个图实际上会有多条平行的边，尽管这里只显示了一条边。
`S1 / \ 3 / \ 1 / \ A----1---B---100---S3 | | 10 10 | | D----1---C \ /
浏览 6提问于2015-08-10得票数 0
我正在学习图，在图中我发现，为了找到从一个节点到另一个节点的最短路径，我们可以使用Dijkstra和Bellman算法。
其中Dijkstra不适用于包含负重边的图。而Brllman可以处理这种包含负重边的图形。
我的怀疑是，我尝试了许多包含负重边的图表，并应用了Dijkstra和Bellman，但是在所有情况下，我都发现了相同的结果，我的意思是没有差别，因为负重边也很好。也许是我的思维过程或者我解决问题的方式是错误的，所以只有我才能得到正确的答案。
我的问题是，谁能解释给我一个有负边的图表，并解释dijkstra和bellman的不同结果。
浏览 1提问于2014-09-25得票数 0
回答已采纳
2回答
最小生成树和最短路径
、、、
我遇到了这样一个问题：
给定一个具有整数权重(正负)的连通有向图，开发一个算法来寻找两个顶点之间的最短路径。
我想我可以使用最小生成树算法，例如kruskal的算法，然后使用可能的dijkstra算法来证明，因为在MST中，每个顶点只有一条进入边，dijkstra的算法甚至可以在负权重下工作。
这听起来很夸张吗？
附注：我很难证明MST包含每个顶点的有向图的最短路径。
浏览 1提问于2012-11-08得票数 0
1回答
这是一个旧的期中考试中的示例问题：
设G= (V，E)是一个连通的无向图，其中边具有与之相关的正整数边权，顶点s∈V是源。提供一个算法，对于每个顶点t，∈V报告从s到t的非递减路径上的最小最后边权重(如果没有这样的路径，则为∞)。一条路径v1，v2，.。。当i= 1，2，...r−2时，如果w(v_i，v_i+1)≤w(v_i+1，v_i+2)，则vr不减。
我认为这个问题需要我想出一个算法，给出一个有起始顶点的图，可以找到最短路径的长度，边的权重随着你沿着路径往下走，到它可以到达的每个其他顶点，这样的想法是正确的吗？
浏览 1提问于2015-11-04得票数 1
我运行了一个路径查找库。QuickGraph，一个开放的图形库，满足了我所有的需求，但我遇到了一个问题。我需要最短路径算法来跳过当前移动代理无法通过的边。我想要的是这样的：
Func<SEquatableEdge<VectorD3>, double> cityDistances = delegate(SEquatableEdge<VectorD3> edge)
{
if(edge.IsPassableBy(agent))
return edgeWeight; // Edge is passable, return its weigh
浏览 10提问于2013-01-14得票数 5
1回答
我完全惊讶于python networkx不支持特定两个节点之间的重路径
我有一个很大的图，~70K节点，每个边都有一个权重属性(权重是>= 0)。
我想要创建一个函数，取源和目标，并返回这个特定的2个节点之间的最重路径。
我尝试过使用all_simple_path并实现了get_weight函数，该函数采用路径并返回总权重，就像一些解决方案中所建议的那样。
但是all_simple_path永远不会以这个图结束，这个图肯定没有任何循环(ran find_cycle函数)，这个解决方案适用于非常小的图。
我在这里和其他地方找到的所有建议的解决方案都返回整个图中最重的路径(开始到结束)，而
浏览 3提问于2020-05-31得票数 0
1回答
我使用networkx加权图来对交通网络进行建模。我试图根据加权边的和找到最短的路径。为了找到这条路径，我使用了Dijkstra路径。当加权边存在平局时，我的问题就会出现。当这种情况发生时，我总是希望从一组连接的路径中选择具有最少边数的路径。Dijkstra path似乎没有做到这一点。
有没有办法确保我可以从一组根据加权边的总和连接起来的路径中选择边数最少的路径？
浏览 5提问于2017-02-04得票数 1
形式上，我们给出了一个图G，图G上每个节点都有一个+ve数。给我们没有循环的有向边。然后，我们被要求回答Q查询，每个查询都要求编辑G上节点的权重，我们必须打印最长权重路径的权重。注意，每个查询都意味着从原始图中编辑一个节点。N<=10^5 & Q<=10^6 .最有效的解决方案是什么？
当然，野蛮人将采取O(n_q)，这是太多。我尝试了2,3种不同的蛮力，这给出了更好的平均时间复杂度，但我可以为每个解决方案找到至少一个测试数据，如果我们反复问，就像O(n_q)一样糟糕。
浏览 1提问于2015-02-08得票数 0
我正在使用python从输入文件创建一个加权图。重点是，我需要清晰的边数(因为这是一个加权图)。我知道
graph.ecount()
没有考虑到这一点。我可以读取文件本身和计数不同边缘的数量，但是我想知道ecount本身是否有一个函数或属性，我可以为ecount设置它来计数不同的边数。请注意，我使用以下代码行来创建图形：
graph= Graph.Read_Ncol(file, names=True, weights="if_present", directed=True)
谢谢
浏览 4提问于2015-09-16得票数 2
回答已采纳
3回答
给定所需的分区数量，分区的大小应该几乎相等。为列表处理这个问题。它们不具有随机性，但那是。我的问题是，我有一个迭代器作为输入，所以shuffle不适用。这样做的原因是我想随机划分图的节点。这个图可能非常大，所以我正在寻找一个不只是创建一个中间列表的解决方案。
我的第一个想法是使用带有随机数函数的作为选择器。但这只适用于两个分区。
浏览 1提问于2010-09-21得票数 0
回答已采纳
1回答
一个具有n个顶点和m个边的加权无向图若对每条边(u，v)的权重小于或等于从u到v的任何其他交替路径的长度，则称为满足三角不等式。
证明了对于这样一个图，所有边的总权重是<= ( MST +1)*MST，其中MST是最小生成树的所有边的总权重。
(提示:不属于最小生成树的图的边的最大可能权重是多少？)
浏览 2提问于2015-10-09得票数 1
回答已采纳
1回答
Dijkstra算法特例
、、、
我正在用Python实现Dijkstra最短路径算法。图是有向的和加权的。图有1070375个顶点。第一项任务是寻找顶点#100562和1070345之间的最短路径。我做到了。我对此没有异议。但是第二个任务是找到这些顶点之间的唯一路径数，它们具有相同的长度和不同的内部顶点。我的问题是，这意味着：之间的唯一路径，具有相同的长度和不同的内部顶点。从100562到1070345可以有很少的路径，或者是唯一的路径，例如，从顶点# 111700到顶点#111704。你能在简单的图表例子上展示它吗？
浏览 5提问于2016-11-26得票数 0
假设给定的图G (有n个顶点，m条边)的最小生成树T和一个权重为w的新边e= (u，v)，我们将添加到G中。
I)检查T是否仍为MST。II)如果不是，给出一个有效的算法来寻找图G+ e的最小生成树。
浏览 4提问于2013-05-29得票数 2
回答已采纳
1回答
我还没能找到任何类似下面的金字塔图的例子。我只是将这个绘制的图像作为一个例子，但我发现的大多数类似的实现都只适用于金字塔或规则的圆圈饼图。
浏览 1提问于2014-12-06得票数 1
我有一个图的顶点的CSV文档和图的边的其他文档，我加载了这些文档并形成了图，我的问题是如何创建一个白色的顶点和边的索引。
我读到使用索引时运行时间较低，需要创建一个计算最短路径的函数。
有什么想法吗？
浏览 1提问于2016-11-07得票数 0
考虑以下策略，将具有负边权的图转换为没有负边权的图。设图中的最大幅值负边权为-k。然后，对于具有权重w的图中的每个边，将权重更新为w+k+1。
为了解决原图中的最短路径问题，我们可以在修改后的图上运行Dijkstra算法，减去增加的权重，得到原图。
这一说法总体上不成立。
这一说法对所有图都是正确的。
对于连通无圈图，这一说法是正确的。
对于具有圈的连通图，这一说法一般不成立。
浏览 0提问于2017-02-20得票数 0
回答已采纳
2回答
在我的经济学研究中，我目前正在处理一个特定的最短路径问题：
给定一个边上有权的有向确定性动态图，我需要从一个源S找到经过N条边的最短路径。图可以有圈，边权重可以为负，并且允许路径多次通过顶点或边。
这个问题有没有一个有效的算法？
浏览 2提问于2018-06-29得票数 4
1回答
Dijkstra算法的多输入
、、、、
Dijkstra算法的输入是一个有向加权图，通常由邻接(距离)矩阵和起始节点表示。 我有两个不同的距离矩阵作为输入，代表两个不同的基础设施(例如，道路和自行车道)。你知道如何修改Dijkstra的算法来使用这两个输入吗？我想用Python实现。 谢谢!
浏览 25提问于2019-06-03得票数 0
2回答
最长简单路径
、、、、
因此，我理解在图中寻找最长的简单路径的问题是NP困难的，因为您可以通过将边权重设置为1并查看最长简单路径的长度是否等于边的数量来轻松地解决哈密顿电路问题。
我的问题是:如果你得到一个图，找到最大边权重m，用m - w替换每个边权重w，并在上面运行标准的最短路径算法，你会得到什么样的路径？这显然不是最长的简单路径，因为如果是，那么NP = P，我认为这样的东西的证明会更复杂=P。
浏览 0提问于2009-04-04得票数 9
回答已采纳
2回答
我有间隔数据：
A = (0,50)
B = (20,500)
C = (80,420)
....
并意识到有一个与这些数据相关的图形，
我想找出从A到G的最有效的路径(假设我知道所有的正顶点权重，wa，wb，wc.)。我需要从A开始，到G，所以最小生成树必须在这些点之间绑定。我们应用程序中的约束之一是，从A开始到以G结尾的间隔必须完全覆盖(没有空白)。我在看，不知道如何指定A和G必须是起始点和端点。
想到的其他一些问题是：
既然这个问题是NP-困难的，如果节点数高的话，我是否应该费心去寻找一个最小生成树呢？有多少个节点会太多？
注意，区间F有一个唯一的区域。换句话说，要完全
浏览 9提问于2015-02-04得票数 2
回答已采纳
给定一些无向边权重图，什么算法可以用来寻找从某个顶点v到另一个顶点w的最短路径？
对于有向边权重图，您可以使用Dijkstra的最短路径算法，但我使用的是无向图，因此它不起作用。
对于不是边加权的图，您可以使用广度优先搜索(BFS)，但我使用的是边加权图，因此它不起作用。
因此，假设它既是无向的，又是边加权的，那么一般的最短路径方法是什么？
浏览 5提问于2019-10-07得票数 0
2回答
我目前正在研究图及其算法，我注意到一个我不知道能确切证明的问题：
如果我们有一个连通的无向图G=(V，E)和每个边都有weight=1，那么每一棵从根建立的最短路径的生成树都是最小生成树吗？
我用做了一些例子，我觉得这个问题的答案是正确的，但是有人可以告诉我如何证明这一点？另一个在我脑海中闪现的问题，是不是另一个方向也是正确的？
浏览 1提问于2015-12-21得票数 3
回答已采纳
给定一个无向无权图，其中一些节点被标记，是否有一种有效的方法来找到节点A和B之间的无标记节点，当它们被标记时会从A到B创建一条“标记”路径？这些“桥”节点的数量应该是最小的。
例如，在下面的图表中，将节点A连接到B有两种最小的方法。一种可能是标记标记为1的节点，另一种可能是标记节点2。
浏览 0提问于2018-03-20得票数 0
回答已采纳
1回答
我正在上课程，其中一个问题是：
假设P≠NP。考虑具有非负边长的无向图。下列哪一个问题可以在多项式时间内解决？
提示:哈密顿路径问题是:给定一个具有n个顶点的无向图，确定是否有一条(无圈的)n-1边完全访问每个顶点一次的路径。你可以利用哈密顿路径问题是NP-完全这一事实。从哈密顿路径问题到下面四个问题中的三个问题，有相对简单的简化。
对于给定的源s和目标t，计算具有n-1边的最短s路径的长度(如果不存在这种路径，则计算+∞)。允许路径包含循环。
在图的所有生成树中，用尽可能最少的叶子数计算一棵树.
在图的所有生成树中，用最小可能的最大度计算一棵树。(回想一下，顶点的程度是入
浏览 0提问于2019-01-08得票数 0
2回答
我在做一个有向图的项目，在这个项目中，边的权重都依赖于变量x，我试图找出x的最小值，这样我的图就不包含任何正权电路。
我的问题是，-and，它可能是相当愚蠢，但我不知道如何-：我如何能够使用改进的Bellman检查是否存在正极电路，而不是负电路？
谢谢。
浏览 4提问于2015-07-09得票数 1
回答已采纳
1回答
我有一个有向加权图G，其中权重是过渡的持续时间。
我使用修改后的DFS编写了两个顶点之间的所有路径搜索算法:搜索将继续进行，直到路径的总权重(其各部分的权重之和)将减少一些值。
我的代码工作在小图，但在大图(|V|=1800，|E|=50870)它冻结。
def find_paths(self, start, end, weight_limit=10):
res = []
def dfs(start, end, path=[], weight=0):
path = path + [start]
if len(pa
浏览 10提问于2016-04-26得票数 1
假设我有一个图，其中最小边权重为−100。我可以将100作为所有边的偏移量，并使用Dijkstra算法吗？
请帮助我理解为什么这样的方法会给出错误的解决方案。
浏览 0提问于2011-09-06得票数 4
回答已采纳
1回答
我试着想出一种算法来找到一条穿越无向图的路径。这不是一条传统的道路，我找不到任何类似这样的事情已经做过的参考资料。
我的目标是找到一条具有最小游动边的路径(顶点之间的跳跃)和这条路径的最大权重(流行度在最小游走边)。该算法首先检查所有具有最小游动边的路径，然后选择这些路径中的哪一条具有最大权重。例如，两个最小行程边路径是{3->4->5}，而{5->6->3}算法应该采用路径2，因为总重量是14，而在第一条是12。
如果有人能给我提供类似材料的参考资料或解决这个问题的方法，那将是非常有用的。
浏览 6提问于2022-11-08得票数 1
2回答
给定一个有向图G、权重、s源顶点和图中每个顶点的dv (从s到v的距离)，我需要找到一个构建最短路径图的算法。
我正在考虑用BFS来处理边，但是我怎么知道哪条边应该在树中，以及如何检查每个顶点的dv是真的。
浏览 0提问于2012-12-24得票数 0
1回答
给出了一个马尔可夫模型，该模型具有一个名为S的开始状态和一个名为F的退出状态，并且该模型可以表示为一个有向图，有一些约束条件：
每条边都有一些权值在(0，1)范围内作为转移概率。
从每个节点得到的边的权重之和为1。
问题是如何排列开始状态和退出状态之间的路径？或者，更准确地说，如何找出概率最高的路径？
一方面，权值是概率的，所以路径越长，乘积越小，一种启发式策略是选择较短的路径和更大的权重候选值，但是这个问题是否可以转化为最短路径问题，或者使用一些量身定制的维特比算法或一些DP算法来解决？
浏览 4提问于2016-08-11得票数 2
2回答
我有一个加权图，我想为这个图计算一个新的加权函数，这样边权是不同的，新图中的每个MST都对应于旧图中的MST。
我找不到可行的算法。我把所有的重量都翻了一倍，但这并不能使它们区别开来。我还试着把权重加倍，用相同的权重在边上添加不同的常量，但这感觉也不对。
新的图将只有一个MST，因为所有的边都是不同的。
浏览 5提问于2017-10-26得票数 2
回答已采纳
1回答
我有一个看似简单的问题要用有向图来解决。给定一个有向图，例如图片中的那个，我需要找到两个“边界节点”(图片中的A和B )之间具有最小“最大成本”的路径。图中的每个节点都有一个要被入侵的“成本”，因此对于每个可能的路径，我们都可以找到最大的成本。例如，在图片中，路径3胜出，因为最大成本小于路径1和路径2的最大成本。
我总是听说Tensorflow是一个可以解决一般图形问题的库，所以我想知道Tensorflow周围是否有任何“随时可用”的库/后端可以让我解决这个问题？
谢谢你，拉斐尔
浏览 19提问于2019-10-25得票数 0
3回答
一本书中说“Dijkstra的算法只适用于有向无环图”。
该算法似乎也适用于有圈的图，只要没有负圈。对吗？
编辑1："Grokking Algorithms“-Aditya Bhargava一书。第七章，第122页。
浏览 3提问于2017-04-13得票数 19
5回答
当图的节点有权时，计算有向非循环图的关键路径的最佳(关于性能)方法是什么？
例如，如果我有以下结构：
Node A (weight 3)
/ \
Node B (weight 4) Node D (weight 7)
/ \
Node E (weight 2) Node F (weight 3)
关键路径应该是A->B->F (总权重: 10)
浏览 0提问于2008-09-20得票数 5
回答已采纳
1回答
考虑以下具有节点和边权的有向图。
是否有一种非NP-硬算法来找出最大得分的路径，其中
score = sum(node weights) - sum(edge weights)
以图为例，最大得分路径为A -> B -> C -> D，最大得分为164 (77+ 27 + 32 + 84) - (44 + 12 +0)。
浏览 7提问于2022-03-23得票数 2
回答已采纳
给定有向JUNG图的两个节点A和B，我想确定从A到B是否有多条路径(不一定是最短路径)。
我只能想到两种方法，两种方法都很费时。
检索连接两个节点的所有路径(问题)，并检查是否有多个节点。
使用类DijkstraShortestPath检索最短路径，然后中断该路径并再次搜索最短路径。如果仍然有一条，那就意味着有多条路径。请注意，这也需要克隆图形，因为我不想更改原始图。
我怎样才能更聪明(也就是更快)做到这一点？
浏览 1提问于2013-04-05得票数 0
回答已采纳
当我想通过timedelta-weighted图在networkx中计算最短路径时，如下所示
import networkx as nx
from datetime import timedelta
G = nx.DiGraph()
G.add_edge(1, 2, timedelta=timedelta(seconds=1))
G.add_edge(2, 3, timedelta=timedelta(seconds=1))
G.add_edge(1, 3, timedelta=timedelta(seconds=3))
nx.single_source_dijkstra(G, 1,
浏览 12提问于2022-02-21得票数 0
回答已采纳
图G是一个无向图，它的所有边的权重都是相同的。u，v是2个给定的顶点，如何在O(|V|)中求出图G中u和v之间的最短路径的个数？
|V|表示G中的顶点数。
浏览 0提问于2014-12-21得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
