我正在尝试将MATLAB转换成python代码。我想知道这两个函数之间的等价性是否正确。我知道这是用于未加权计算的，这正是我想要的，但是python函数中的源和目标节点在哪里呢？
MATLAB
d = distances(G,s,t,'Method',algorithm)
所有节点对的最短路径距离
PYTHON
path_lengths = dict(nx.all_pairs_shortest_path_length(G))
浏览 5提问于2022-01-18得票数 -1
1回答
Dijkstra算法特例
、、、
我正在用Python实现Dijkstra最短路径算法。图是有向的和加权的。图有1070375个顶点。第一项任务是寻找顶点#100562和1070345之间的最短路径。我做到了。我对此没有异议。但是第二个任务是找到这些顶点之间的唯一路径数，它们具有相同的长度和不同的内部顶点。我的问题是，这意味着：之间的唯一路径，具有相同的长度和不同的内部顶点。从100562到1070345可以有很少的路径，或者是唯一的路径，例如，从顶点# 111700到顶点#111704。你能在简单的图表例子上展示它吗？
浏览 5提问于2016-11-26得票数 0
1回答
我有一个算法，可以在不经过N中的顶点的情况下找到源S和目的地D之间的路径。现在我想修改该算法，以找到源S和多个目的地之间的所有最短路径。 # Python implementation to find the
# shortest path in the graph using
# dictionaries
# Function to find the shortest
# path between two nodes of a graph
def BFS_SP(graph, start, goal,N):
explored = []
# Queue for tr
浏览 38提问于2021-07-23得票数 0
回答已采纳
4回答
我正在实现一个由100,000+节点组成的巨大的有向图。我刚开始学习python，所以我只知道这两种搜索算法。如果我想找到任意两个节点之间的最短距离，哪一个会更有效？有没有其他我不知道的更好的方法？
谢谢您抽时间见我
浏览 0提问于2013-05-23得票数 0
回答已采纳
1回答
背景
我在一个有向加权图上执行一个迭代流量分配(ITA)，图的节点为12k，边为25k。在ITA中的四个迭代的每一个阶段，我都必须找到一个原点和一组目的地之间的最短路径(即所有的原点)。伪代码如下所示：
for iteration in iterations:
for origin in origins:
paths = find the shortest paths between origin and destinations
for destination in destinations:
for each edge bet
浏览 1提问于2020-09-26得票数 0
我有几个Python脚本，它们计算各种网络度量。
给定一个图(G)，第一个脚本计算每个节点到所有其他节点的平均最短路径，并将其存储在Nx1矩阵(L)中。 Python库中使用了贾克斯特拉算法的一个实现，用于：
for i in range(num_nodes):
for j in range(num_nodes):
dj_path_matrix[i,j] = nx.dijkstra_path_length(G, i, j)
L = np.sum(dj_path_matrix, axis=0)/(num_nodes - 1)
给定相同的图(G)，第二个脚本使用库中Bra
浏览 3提问于2017-03-24得票数 0
回答已采纳
我使用的是python 2.7和networkx。
我有一个相当大的网络，我需要找到起点和目的地之间的所有路径(不仅仅是最短路径)。由于我的网络很大，我想在一些限制条件下加快速度，例如路径长度、成本等。
我正在使用networkx。我不想使用all_simple_paths，因为使用all_simple_paths之后，我必须根据路径长度(其中的节点数)或路径的成本(基于弧成本)来过滤所有路径。过滤所有路径对于大型网络来说是非常昂贵的。
我真的很感谢任何人的帮助。
浏览 16提问于2016-09-15得票数 0
我的问题是：
我有一个无向图。每条边都有一个成本(或重量)。其中一个节点被标记为S。我想从S开始，至少访问每个节点一次。允许多次访问节点。允许多次沿边缘旅行，尽管这将使解决方案更加昂贵--以3倍的成本沿边旅行将使整个路径的成本增加6倍。这个图有一些“死胡同”的节点，所以有时我们不得不不止一次地遍历一个边。
什么是快速算法来做到这一点？这是一个众所周知的问题吗？
我要找的是：
相当快--我们这里讨论的图的相对大小是40-50个节点的顺序。所以这个算法希望不会超过10-15秒。
合理的最优--我不是在寻找绝对的最优性。任何有趣的启发式引导搜索，以使解将接近最优是足够好的。
我将用python写这篇
浏览 3提问于2012-09-05得票数 4
2回答
有没有办法在pydot中实现这一点？
下面是一个例子：
输出的点文件
strict graph g{
"A" -> "B";
"B" -> "C";
"C" -> "D";
"D" -> "E";
}
Python
print(num.start)
>>> A
print(num.steps)
>>> ["a,b","b,c","c,d","d,e
浏览 3提问于2011-04-08得票数 2
回答已采纳
只接受普通向量作为输入。但我只有一个距离矩阵。还有其他Python模块来处理这个问题吗？
浏览 2提问于2016-02-26得票数 0
回答已采纳
1回答
我有一个python应用程序，它消耗了大量的数据。为了跟踪我安装的guppy的内存使用情况，并在一个时间单位之后打印堆，我在报告中看到了以下内容。
Partition of a set of 43325494 objects. Total size = 7524458264 bytes.
Index Count % Size % Cumulative % Kind (class / dict of class)
0 2556102 6 2678794896 36 2678794896 36 dict of cocotb.binary.BinaryValu
浏览 1提问于2019-12-21得票数 1
2回答
我正在做一项任务，它让我遍历一个简单的正方形图，目的是积累最少的危险。终点很简单:从左上角到右下角。我只限于水平和垂直移动之间的顶点。地牢里的每个房间(图上的每个顶点)都有一个特定的危险等级。
示例：
0 7 2 5 4 0 -> 1 -> 1 -> 2 -> 2 -> 1 -> 3 -> 1 -> 0
1 5 1 2 1
1 2 2 1 1
1 9 5 3 5
1 1 9 1 0
我一直在抛出使用优先级队列的想法，但我仍然不知道如何，确切地说，我会在第一时间使用那个P。
我可以尝试Dijkstra的算法，但我不是计算节点之间的距离，而是
浏览 0提问于2015-05-12得票数 1
回答已采纳
我有几个节点(无向图，双向图) ...每两个节点都有一个距离...
1-如何使用QuickGraph创建该网络?2-计算两个节点之间的最佳最短路径的正确算法是什么(考虑到之前可能会传入其他节点，例如:最佳路径A->B，传入C和D)
谢谢
浏览 3提问于2010-03-04得票数 2
回答已采纳
1回答
我需要一种在有向图中找到第二最短路径的方法，在第二最短路径的顶部不能完全包含最短路径。我知道dijkstra algoritm算法，但我无法想出一个简单的方法来改变算法，让我在合理的时间内获得第二短路径。算法，子代码或c++示例，三者之一将非常感谢。
浏览 3提问于2016-06-12得票数 2
1回答
给定G=(V，E)，即每条边都有这三种颜色(绿色，红色，蓝色)中的一种。如果一条路径包含所有三种颜色，我们称其为“有色路径”。
Input: graph G(V,E),weight function w:E->Q+ , colored edges and vertices s .
output: algorithm that finds for every vertices v, a shortest path from s
that is Colored path
我的解决方案是遍历该图，并为每个顶点计算路径具有的颜色数量。创建名为G1、G2、G
浏览 16提问于2017-01-30得票数 2
回答已采纳
2回答
用A*算法求几条最短路径
、、、
我正在制作一个路由应用程序，它使用A*算法来查找路由。我想提供的不只是一条路线，还有几条替代路线。例如，仅比最佳路由稍长一点的路由。
由于A* (和其他许多)只找到一条路线，我如何搜索这些替代路线？我应该使用其他算法吗？
浏览 0提问于2015-02-26得票数 1
基本最短路径问题和最短路径问题有什么区别？
一个最短路径问题，通过在图中找到从源节点到目标节点t的最短路径来解决。
一个简单的最短路径问题，通过在图中找到从源节点到目标节点t的最短路径，使得最短路径上的每个弧最多使用1次。
什么是基本的最短路径？
浏览 3提问于2020-03-19得票数 1
回答已采纳
1回答
我有一个有5个节点的完整图G，我必须找到G(随机选择的节点)的直径，并用红色绘制这个直径。我如何使用Networkx和Python来做到这一点？这些是我的尝试。另外，我需要说的是它们更多，但唯一的区别是我尝试使用其他函数(子图，算法节奏等)而不是最短路径。另外，我需要解释随机节点意味着您随机选择直径的起点
import networkx as nx #1 attempt
G = nx.complete_graph(5)
dg = nx.shortest_path(G)
edge_colors = ['red' if e in dg.edges else 'bla
浏览 0提问于2021-05-13得票数 1
1回答
我想用A*搜索来解决难题。如何定义g(n)和h(n)？H和g应该是什么？？
我想在python中编写这些代码，但是如果有任何伪代码，我们将不胜感激。
浏览 3提问于2015-03-14得票数 0
回答已采纳
3回答
我正在使用networkx来处理图形。我有一个很大的图(里面有近200个节点)，我试图找到两个节点之间的所有可能的路径。但是，据我所知，networkx只能找到最短路径。我怎样才能得到最短路径，而是所有可能的路径？
UPD:每个节点路径只能包含一次。
UPD2:我需要一些类似find_all_paths()函数的东西，如下所示: python.org/doc/essays/graphs.html，但是这个函数不能很好地处理大量节点和edged =(
浏览 2提问于2010-04-09得票数 9
回答已采纳
2回答
我使用netwrokx计算不同顶点之间的最短路径，使用Dijkstra算法。我有一个例子，我想连接三个不同的顶点(例如，A，B和C在一个无向图中)。首先，我找到了从A到B的最短路径，然后我想要找到从A到B的路径的最短路径。到目前为止，我尝试的是从A到B路径的所有节点到C的最短路径长度，然后计算出从节点到给定最小路径长度的最短路径。这是计算密集型的，因为路径可能有多达200到300个节点。
有人能给我一个提示吗?我如何改进方法？或者更容易找到从已有的边缘到目标的最短路径？
浏览 1提问于2018-08-15得票数 2
回答已采纳
用Floyd where算法求出图中s和t到v之间的所有最小路径的总个数，其中s、t和v是图的节点。提前谢谢你的回答。
浏览 5提问于2017-07-20得票数 0
回答已采纳
2回答
我使用适当实现的dijkstra算法计算出最短路径。它通过B，C，D和E从A到F，所以整个最短路径是A，B，C，D，E，F。
现在我想从G到F。当从队列中弹出C时，我意识到它是通往F的最短路径的一部分，这是否意味着我也知道从G到F的最短路径是G，H，C，D，E，F。
浏览 2提问于2015-08-28得票数 0
回答已采纳
1回答
大地图上的寻路
、、、
我正在创建一个10,000 * 10,000地图的游戏。
我希望用户能够设置一个位置，并让计算机立即找到最佳路径。
然而，由于映射是10,000×10,000，所以有100,000,000个节点，通过诸如A*或Dijkstra的传统方法来找到这条路径将需要大量的内存和很长的时间。
所以我的问题是:我怎样才能找到最佳路径？
我正在考虑的算法将把世界分成100个部分，每个部分有1,000,000个节点。然后，每个部分将被划分为100个子部分。这将重复进行，直到每个子部分包含100个节点。然后，该算法将找到部分的最佳路径，然后是子部分，然后是子子部分，直到找到最佳节点集。这行得通吗?有没有更好的办法
浏览 83提问于2016-05-27得票数 21
回答已采纳
1回答
网络x图与弗洛伊德战争
、、、、
我是Python的新手。我有一个类似于这个的映射，我希望使用网络x创建从每个节点到每个其他节点的最短路径。
shp = nx.read_shp("../Shapefiles/Shapefiles/Station_in_Corridors/Group_1.shp")
G = nx.DiGraph()
for data in shp.edges(data = True):
G.add_edge(data[0],data[1],weight = data[2]["Length_Km"])
nx.floyd_warshall(G)
pos = nx.sprin
浏览 2提问于2018-11-23得票数 0
1回答
BGP最佳路径选择算法
、、、、
根据这个思科文档(https://www.cisco.com/c/en/us/support/docs/ip/border-gateway-protocol-bgp/13753-25.html)，在BGP从可用列表中选择第一个有效路径之后，在列表中的13个中，最短AS_PATH是排序中的第4个算法。上面写着：
BGP将第一个有效路径指定为当前最佳路径。然后BGP将最佳路径与列表中的下一个路径进行比较，直到BGP到达有效路径列表的末尾。
为了方便起见，我列出了它列出的算法：
重量:最高
本地偏好:最高
网络或聚合:本地起源
AS_PATH:最短
原产地类型:最低原产地数
多出口鉴别器:最低
eB
浏览 0提问于2020-11-24得票数 1
回答已采纳
4回答
使用下面的代码，我试图找到第二条最短路径/第k条最短路径.
// Run Dijkstra's algorithm on given graph
public static void shortestPath(GraphModel graph, int source, int destination, int numberOfVertices)
{
// create min heap and push source node having distance 0
PriorityQueue<NodeModel> minHeap
浏览 0提问于2019-07-17得票数 1
我刚刚开始学习图的算法，更具体地说-- Floyd-Warshall算法。在中查看修改后的允许路径重建的算法，我注意到它保留了中间节点，而不是更符合逻辑的方式(在我看来)-保存下一跳。此外，在课程手册中，该方法被保存为倒数第二个节点。为什么要以这种方式保存路径？
浏览 0提问于2013-11-08得票数 0
1回答
对于一个学校作业，我试图理解Neo4j是如何工作的，到目前为止，我已经能够理解其中的大部分，但由于某种原因，我无法排除一条道路。
我做了一个测试任务，正在做的道路，可以使用的城市->城市。现在，我想排除如下情况下的路径：
找出从乌得勒支到鹿特丹的所有路线，这些路线中没有古达
我想出了许多解决方案，但它们都不起作用，最近我找到了所有的路径，包括Gouda路径和下面的代码
MATCH (Utrecht {Naam:"Utrecht"}), (Stad)-[:CONNECTIE_MET]->(Rotterdam:Stad{Naam:"Rotterdam"}
浏览 3提问于2016-03-24得票数 0
回答已采纳
2回答
给定一个无向(无长度)图G=(V，E)，具有|V|=n和|E|= m，以及两个顶点v，w，找到输出G中最短v-w-path的算法，运行时间应为O(m+n)
我一直在解决这个问题，但是很难让运行时间是O(m+n)
因为这个图既是无向的，也是无权重的，所以我尝试了这种方法。使用BFS确定最短v-w-path的长度。然后使用DFS求出使得两个节点相连且路径长度等于BFS的输出的v-w最短路径的数目。但该方案的运行时间为O(m+n)+O(m+n)。
此外，我还尝试修改Dijkstra算法。存储访问节点集合中添加节点时的最短路径长度和最短路径个数。而且我被运行时间的计算所困扰。
浏览 0提问于2014-09-13得票数 0
回答已采纳
既然最短路径已经是“最短的”，那么它有可能比MST中的任何其他路径都长吗？我知道这两个顶点之间的路径通常比两个顶点之间的最短路径长，但它能更短吗？
浏览 18提问于2020-02-05得票数 1
2回答
我在LightOJ中发现了一个问题，该问题是在从节点1到节点n的图中找到第二条最短路径(图中有n个节点标记为1到n)。现在，问题说我可以回溯找到第二条最短的路径。其中一个例子如下：
边缘从节点1到2，花费100。
边缘从节点2到3，花费300。
边缘从节点1到3，成本50。
这个测试的答案是150，这个路径1->2->1->3。我知道Dijkstra算法。但我找不到任何关于怎么做的事。我很抱歉，如果这是老话题，但我当我搜索它，我找不到任何东西。
更新:我读了这个问题。我的问题和它不同，因为在这个问题中，我可以使用边缘两次。我将从节点1转到2，然后返回到1。
浏览 1提问于2016-06-28得票数 3
我有一段使用多进程和访问数据库的python代码。它在大多数情况下都能正常工作，但有时会产生错误。该错误最初是
File "/usr/lib/python2.7/multiprocessing/pool.py", line 528, in get
raise self._value
pg.OperationalError: can't rollback
或
File "/usr/lib/python2.7/multiprocessing/pool.py", line 528, in get
raise self._value
pg.In
浏览 3提问于2013-11-26得票数 4
回答已采纳
我不是要求一个算法来检查图中负圈的存在(Bellman Ford或Floyd Warshall可以这样做)，而是在图包含至少一个从源顶点可以到达的负圈，并且从负圈可以到达目标顶点的情况下，是否存在多项式时间算法来寻找两点之间的最短路径。
浏览 3提问于2013-09-02得票数 2
回答已采纳
我有一个由节点和边的权重组成的网络。我都认识他们。我得到了一个“包”，我知道它目前正在节点A上从B到C。如何获得当前可以遍历的最小路径(下一个和以前的节点)？
浏览 3提问于2020-06-04得票数 0
回答已采纳
1回答
我想要计算一个无向加权图中每个节点之间的所有最短路径。我目前正在使用来自graph_tool.topology.shortest_distance python库的graph_tool，但它似乎只运行在一个内核中。有没有办法让它并行运行？
浏览 4提问于2021-08-04得票数 0
如何使用Floyd-Warshall算法获得从顶点1到顶点10的每条具有相同权重的最短路径？我设法得到了从顶点1到顶点10的所有最短路径的总数。
public static int[][] shortestpath(int[][] adj, int[][] path, int[][] count) {
int n = adj.length;
int[][] ans = new int[n][n];
copy(ans, adj);
// Compute incremently better paths through vertex k.
for (i
浏览 5提问于2018-04-18得票数 3
1回答
我对codding不太了解，但我了解基本的Python。我想通过编写一个解决下一个问题的程序来挑战自己--考虑到一家商店给你3种选择--每天X美元、每月Y美元或每年Z美元，假设我想要足够的时间，哪种组合对我来说是最好的？
现在，就我所能理解的而言，我这里有一个基本的组合问题来创建一个组合树，并且需要一些最短路径算法(Djikstra，Bellman-Ford.？)寻找最佳选择(“较短”、“较便宜”)
请帮我找到我需要处理这个问题的地方。
浏览 4提问于2015-03-21得票数 1
回答已采纳
使用库，我定义了一个MultDiGraph。然后计算出两个给定节点之间的最短路径。因为我的图有平行边，所以我想知道构成最短路径的边的键。下面是一个例子：
import networkx as nx
G = nx.MultiDiGraph()
G.add_edge('a', 'b', key=0, weight=1)
G.add_edge('a', 'b', key=1, weight=2)
G.add_edge('b', 'c', key=0, weight=1)
shortest_path =
浏览 5提问于2022-02-24得票数 0
回答已采纳
1回答
我看到了这个令人困惑的问题，我想我会尝试编写一个Python程序来解决它。任务是将“四”转换为“五”，在每一步形成一个新的四字母单词，在每一步替换一个字母，以尽可能少的步骤。
但是事实证明，我不知道如何优化递归，所以我在这里发帖寻求帮助。我对为什么更改past的代码需要放在函数的顶端感到困惑，但我也想知道如何在一般情况下加快速度。现在，max_depth在我的计算机上每走一步就需要大约10倍的时间。
不会有任何匹配，直到你改变max_depth -我不希望任何人复制粘贴和滞后。根据令人费解的说法，在深度5处应该有一个解决方案。但是，我的words文件没有Foud或单词Fous，这个答案使用这个
浏览 0提问于2019-06-13得票数 7
回答已采纳
你好，我在C Dijkstra的算法中实现了最短路径，但是我需要返回n条最短路径，任何人都知道我能做什么。
我的dijkstra功能：
int * Dijkstra(graph **g, int totalVertex, int vStart) {
int i;
int *distance = (int*) malloc(totalVertex * sizeof (int));
int *last = (int*) malloc(totalVertex * sizeof (int));
int *visited = (int*) calloc(totalVertex, size
浏览 1提问于2012-05-13得票数 2
1回答
假设我们在一个无向循环加权图中有一条路径。假设我们有一个引擎可以在这样的图中找到从节点A到节点B的路径，有没有一种简单的方法/算法来计算出从A到B的给定路径是否比从A到B的任何其他不相交的路径至少好X%？我所说的不相交是指两条路径不能共享任何边。
浏览 1提问于2011-10-08得票数 1
回答已采纳
1回答
我有一个像加权迷宫一样的网格，我需要在没有任何关于迷宫的先验知识的情况下找到通向实体的最短路径。
像A* expect priot knowledge这样的算法在环顾四周时会“跳来跳去”，但当我有一个机器人的时候，这是不可能的。
我的第一个想法是最初使用BFS探索整个迷宫，然后在探索的迷宫上应用A*，以找到考虑权重的最短迷宫。但这似乎太天真了。
有没有人能给我一些适合这个问题的算法？
浏览 0提问于2018-12-10得票数 3
1回答
我的理解是，BFS和DFS是图遍历算法，而其他算法(如A*和dijkstra )则用于在图的两个节点之间寻找最短路径。但是在一些地方，我认为BFS和DFS也被称为最短路径查找算法。请详细说明图遍历算法与最短路径查找算法的区别。谢谢!
浏览 6提问于2022-05-06得票数 0
1回答
所有对最短路径问题
、、、、
我已经写了这个程序，它使用邻接矩阵实现了一个有100个节点的图。我还使用了Floyd-Warshall算法来为所有100个节点找到所有对的最短路径。现在，我想将100 x 100矩阵压缩为10 x 10矩阵，该矩阵仅包含public static final int A = 100...public static final int W = 66指定的10个索引的所有对最短路径。我应该如何压缩数组？我已经开始构建一个名为arrayCondenser的新方法，但是有没有更简单的方法呢？
public class AdjacencyMatrix
{
public static
浏览 11提问于2017-03-06得票数 1
1回答
O(E)最短路径
、、、
有没有一种方法可以在O(E)中找到一个任意权重的图中从单个源到顶点的最短路径，但如果最短路径只有7条或更少的边，你只需要担心这个问题。
贝尔曼-福特算法的最佳运行时间为O(E)，这适用于这里吗？
浏览 1提问于2017-11-09得票数 1
1回答
我正在设置一个图形机器学习应用程序使用Ocatvian图形ML工具集。在这种情况下，我试图设置最短路径库。在Tesnforflow后端出现错误时，它失败了。
AttributeError: module 'tensorflow_core._api.v2.nn' has no attribute 'rnn_cell'`
请在下面找到详细的错误日志：
文件"/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/runpy.py"，第193行，在_run_module_as_m
浏览 5提问于2019-11-26得票数 0
2回答
如果我们将图G反转到G‘，并从源顶点't’对G‘运行Dijkstra算法，这个算法会给出从所有顶点到G中't’的最短路径吗?有人能证明或找到反例吗？
浏览 6提问于2018-11-02得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
