1回答
我想找出二元矩阵两点之间的最短路径。
由用户给出矩阵的来源和目标。我们只能选择矩阵中1的位置，也可以对角、左、右、上、下移动。
如果移动是对角的，代价是根2，否则是1。所以我想要一个算法，如何找到它。
浏览 5提问于2013-02-14得票数 0
1回答
在一个标准的线性赋值问题中，我可以用匈牙利算法实现O(n^3)。如果添加了额外的约束怎么办？示例：
具有4代理的“正则”LAP有约束矩阵
结果向量b=111。
匈牙利算法将像预期的那样解决这些问题。但是，如果添加了另一个约束，例如约束矩阵是
结果向量b=11 1 1 1 0？
也就是说，除了在标准线性和约束下最小化成本函数之外，我还必须考虑如下约束
此和产生上述附加矩阵中的最后一行。
显然，由此产生的约束矩阵不再是完全单模的。当然，标准的MILP会解决这个问题，但是它是NP难的。我的问题是:是否有一种类似匈牙利的算法，可以在多项式时间内解决这个问题？
浏览 9提问于2017-10-23得票数 1
回答已采纳
1回答
我有一个三角形矩阵NxN表示顶点之间的距离(顶点我只与向量j>i连接)，我想从第一个到最后一个对路径进行采样，并使用它作为训练样本。有算法来做吗？在A*中交换min->样品是否足够？
浏览 0提问于2020-01-13得票数 2
2回答
是否有可能热启动APSP问题的任何众所周知的算法(Dijkstra/Floyd-Warshall等)，以便能够降低时间复杂度，并潜在地减少计算时间？
假设该图由一个NxN矩阵表示。我只考虑了一个或多个矩阵条目( << N)的变化，即对算法过程的任何2次调用之间的对应顶点之间的距离。我们可以使用第一次调用的解决方案和矩阵的增量更改来加快第二次调用算法的计算速度吗？我主要研究的是稠密矩阵，但如果有稀疏矩阵的已知方法，请随时与我们分享。谢谢。
浏览 2提问于2014-02-07得票数 6
2回答
我读了floyd warshall算法1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each vertex v 3 dist[v][v] ← 0 4 for each edge (u,v) 5 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9
浏览 3提问于2015-06-15得票数 6
1回答
如果我们知道或不知道给定图中两个节点之间的路径长度，如何一次追踪它们之间的路径？(通过考虑邻接矩阵)
在邻接矩阵和广度优先搜索中，哪种方法更有效？
你能给出算法步骤吗。
提前谢谢你，卡玛拉。
浏览 0提问于2013-06-04得票数 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回答
竞争下的预处理最短路径
、、、、
证明了如果P是u与v之间的最短路，那么每个子路也是最短路。给定连通图，我希望预处理矩阵中每对节点之间的最短路径，这样：
Pathu，v= Pathv，u
如果x，y在路径中，v，那么路径，y是路径的子路径，v。
我不知道一个算法或一个证明，实际上，我不知道这是否是可确认的。任何想法都是welcome.Thank你。
浏览 2提问于2016-07-04得票数 1
1回答
邻接矩阵中的路径查找
、、、
给定一个邻接矩阵，你如何找到两个节点之间的最短路径，同时至少遍历每一点一次，并返回所需的移动次数？
示例
给定这个数组
int[][] points = { { 0, 1 },{ 0, 2 },{ 1, 2 },{ 1, 3 },{ 3, 4 } };
我做了一个类似这样的相邻矩阵..。
0 1 2 3 4
0 [0] [1] [1] [0] [0]
1 [1] [0] [1] [1] [0]
2 [1] [1] [0] [0] [0]
3 [0] [1] [0] [0] [1]
4 [0]
浏览 2提问于2013-04-07得票数 0
3回答
我们得到一个加权图G和它的最短路径距离的矩阵Δ。因此，Δ(i，j)表示从i到j最短路径的权重(i和j是图的两个顶点)。初始给定的增量包含最短路径的值。突然，边E的权重从W减少到W‘。如何更新O(n^2)中的增量(i，j)？(图的顶点的n=number)问题不是再次计算具有最佳O(n^3)复杂度的所有对最短路径。问题是更新增量，这样我们就不需要重新计算所有对的最短路径。
更清楚的是:我们只有一个图和它的增量矩阵。增量矩阵只包含最短路径的值。现在我们想要根据图中的变化来更新增量矩阵:减少边权重。如何在O(n^2)中更新它？
浏览 2提问于2010-12-17得票数 4
1回答
得到的矩阵=一个矩阵，其中mati是以顶点I为源，顶点j为目标的最短路径。
我写了我自己的约翰逊算法的实现，我想知道它是如何处理负边的？最后，我所获得的距离矩阵与我运行弗洛伊德-沃尔时得到的距离矩阵不一样。这一点很明显，因为我们调整了图表的权重。这是否意味着Johnson的算法并不能帮助我们找到最短路径的代价，而只是哪条路径是最短的？另外，如果结果矩阵中的顶点A和顶点B之间有一条路径，而在成本为0的顶点A和顶点C之间又有一条路径，这是否意味着B和C与A的距离相等？
浏览 3提问于2018-12-01得票数 0
回答已采纳
我有一个简单的图表，我需要找到这个图表的启发式成本。
图是(矩阵表示)：
0 1 2 0 0 0 0
1 0 0 3 3 2 0
3 0 0 2 0 0 0
0 3 1 0 1 0 0
0 3 0 1 0 6 0
0 2 0 0 6 0 2
0 0 0 0 0 2 0
图片：
括号中的值表示当前目标顶点的顶点的启发式成本。
绿色顶点是开始，红色顶点是目标。
我创建了这个遗传成本矩阵：
0 2 6 3 1 9 5
9 0 2 4 6 4 1
1 3 0 5 2 9 4
3 1 5 0 1 7 8
0 6 2 1 0 10 14
2 1 6 3 7 0 5
1 4 3 2 1 3 0
我
浏览 0提问于2014-05-04得票数 0
我有连接"1“(连接4”北、南、东、西“)的(3x4) M矩阵，例如：
M=[0 1 1 1;
1 1 0 1;
0 1 0 1];
指标元素: idx=2 4 5 6 7 10 11 12；(8元素)。M可以看作是黑白像素的矩阵。
有办法解决它的(8x8) D矩阵的白像素分离吗？(expl:带有idx=2和12的元素是由5个白色像素分隔的6步apart= )
D=[0 2 1 2 3 4 5 6;
2 0 1 2 3 4 5 6;
1 1 0 1 2 3 4 5;
2 2 1 0 1 2 3 4;
3 3 2 1 0 1 2 3;
浏览 1提问于2017-09-17得票数 0
回答已采纳
2回答
我对量化投资领域非常陌生，但我想知道矩阵是否可以用来识别多货币兑换中的套利机会。这将是一种最短路径查找问题或用于不同其他问题集中的最小成本算法。
浏览 0提问于2012-07-04得票数 4
1回答
我试图从Skiena的算法设计手册中解决以下问题
8-16考虑一个城市，其街道由X，x，Y网格定义。我们感兴趣的是从网格的左上角走到右下角。不幸的是，这座城市有着糟糕的社区，我们不想走进这些街区的十字路口。给出了一个坏的X×Y矩阵，其中BADi，j=“是”当且仅当街道i和j之间的交点在一个邻域以避免。(c)给出一个O(XY)算法，以在网格中找到避免不良邻域的最短路径。您可以假设所有块都具有相同的长度。对于部分信用，给出了O(X^2*Y^2)算法。
这个问题来自于关于动态规划的章节，在“图问题”的标题下。我知道我可以把它建模成一个无向无权图，它包含所有“好”交点和相邻“好”顶点之间的边的顶
浏览 1提问于2017-01-04得票数 0
我有一个任务是实现Dijkstra的算法。我们得到了将图作为邻接矩阵输入的框架代码，但被告知我们的解决方案必须在O(MlogN) {M边，N顶点}中运行。我知道PQ和list结构是如何实现这一点的，但我不知道如何在我的例子中避免O(N^2)解决方案。走出矩阵的唯一方法是遍历每一行和column...right？
浏览 2提问于2012-11-27得票数 2
回答已采纳
假设下面的矩阵是一个具有3个节点的有向图邻接矩阵。
A=[.35 .076 .12;.0054 .83 .09; .31 .92 .019]
如何在matlab或ucinet中找到两个特定节点之间的最强路径？
我需要一些方法来告诉matlab找到两个节点之间的每条可能的路径，然后将每条路径中的边的权重相加，找到最大的加权路径，然后显示该路径。例如，如果我们考虑矩阵A，并希望找到从节点1到节点3的最强路径，我们有两条可能的路径:一条从节点1到节点3的直接路径，以及一条从节点1到节点2和节点2到节点3的路径。在第一条路径中，我们有A(1,3)=.12，对于第二条路径，我们有A(1,2)+ A(2,
浏览 1提问于2013-11-04得票数 1
1回答
如果节点是直接连接的，就有n个节点，节点之间也有边。每个边没有重量和方向(如果节点a和b连接，它意味着双向连接，而不是单向连接)。
基于该图，我们可以绘制出二维数组A.An-1的邻接矩阵.因此，问题是如何返回最短路径。如果没有路径，应该返回空路径。而路径应该使用链接列表返回。
|A B C D E
A|0 1 0 1 0
B|1 0 1 0 0
C|0 1 0 1 0
D|1 0 1 0 1
E|0 0 0 1 0
因此，基于上面的矩阵，从C到E的最短路径是C，D，E，而从A到C的最短路径是A，B，C。
我们应该使用具有O(n^2)时间复杂度的伪码。我简单地猜BFS方法会很棒。
浏览 2提问于2019-09-08得票数 0
回答已采纳
1回答
我有一个矩阵：
1 2 3 4 5 6
1 0.7431 0.2769 0.0000 0.1869 0.2760 0.9597
2 0.2769 0.0462 0.0344 0.4898 0.6797 0.3404
3 0.0000 0.0344 0.4387 0.4456 0.6551 0.0000
4 0.1869 0.4898 0.4456 0.6463
浏览 1提问于2016-02-23得票数 1
回答已采纳
如何确定两个节点之间的最短路径，给定图的节点间最短距离矩阵？
例如，我有4个节点和最短距离矩阵(M)。
0 4 5 8
4 0 6 3
5 6 0 2
8 3 2 0
m(i，j)是节点i和节点j之间路径的距离，它不需要是节点i和节点j之间的边缘。
有人能指点一下如何做到这一点吗？提前谢谢你。
浏览 4提问于2015-11-02得票数 4
回答已采纳
1回答
计算网格中各点组合之间的距离
、、、、
我正在寻找一个有效的解决以下问题的办法。这应该适用于python，但不一定是在python中。
我有一个2D矩阵，矩阵的每个元素代表一个二维正交网格中的一个点。我想要计算网格中点对之间的最短距离。如果网格中没有“障碍”，这将是微不足道的。
一个数字有助于解释：
图中的每个单元格都是矩阵的一个元素(矩阵是方形的，但可以是矩形的)。灰色细胞是障碍，任何两点之间的路径都必须绕过它们。绿色细胞是我感兴趣的。我对红细胞不感兴趣，但是一条路可以穿过它们。
像A和B这样的点之间的距离计算起来很简单，但是如何计算A和C之间的路径，如图中所示？
我读过关于的文章，但是由于我使用的是一个相当大的网格，通常是
浏览 2提问于2017-12-15得票数 1
回答已采纳
我一整天都在努力理解Dijkstra的算法，并实现了，但没有明显的结果。我有一个城市及其距离的矩阵。我想要做的是给定一个起点和一个终点，找到城市之间的最短路径。
示例：
__0__ __1__ __2__
0 | 0 | 34 | 0 |
|-----|-----|-----|
1 | 34 | 0 | 23 |
|-----|-----|-----|
2 | 0 | 23 | 0 |
----- ----- -----
我开始想知道是否有其他方法来解决这个问题。如果我从原点开始应用Prim算法，然后遍历创建的整个树
浏览 2提问于2011-03-21得票数 4
回答已采纳
在一个简单的匹配-3游戏中，用一个方形的宝石矩阵创建和丢弃新的宝石是相当简单的:当需要的时候，我在矩阵之上生成那些宝石，然后我让它们落入主矩阵，模拟这种常见的从天花板掉下来的行为。
现在让我们想象一下，我有一个矩阵，里面有一些岩石型宝石，那些永远不会从它们的位置移动的宝石，我已经通过一个“强大”的宝石清除了整个专栏。我有这样的事情：
OOO OOO
OOO OOO
OOO OOO
OOO OOO
OOX XOO
OO OO
O O
OOOOOOO
这里，O是一个普通的宝石，而X是一个岩石宝石，它固定在矩阵中，不会从它原来的位置移动。
当新的宝石流入这个矩阵时，它们最终会向左或向右移
浏览 0提问于2014-03-24得票数 2
回答已采纳
1回答
中间中心性的时间复杂性？
、、、
如果给出图的最短路径前驱体矩阵，计算的时间复杂度是多少？
前身矩阵单元如下所示：
如果节点i与节点j直接连接，则小区中的值为0；
如果节点i和节点j未连接，则小区中的值为-1；
否则单元格=前身( j )--如果有一条最短路径，这只能是一个前身；如果i和j之间有多条最短路径，则可以是一个前导数组。
谢谢你的回答，
我对Brandes算法很熟悉。但是，Brandes算法将计算网络中所有节点的间度。我认为计算一个顶点的CB所花费的时间与计算所有顶点的CB的时间是相同的，因为Brandes算法不能适应这种情况。
因此，我的想法是存储前任矩阵，并且能够计算某个顶点的CB (而不必
浏览 1提问于2011-06-30得票数 0
2回答
用A*算法求几条最短路径
、、、
我正在制作一个路由应用程序，它使用A*算法来查找路由。我想提供的不只是一条路线，还有几条替代路线。例如，仅比最佳路由稍长一点的路由。
由于A* (和其他许多)只找到一条路线，我如何搜索这些替代路线？我应该使用其他算法吗？
浏览 0提问于2015-02-26得票数 1
给定一个距离矩阵D，其中di表示从i到j的最短路径，并且所有边权重都为正。另外，
d[i][i] = 0 and
d[i][j] > 0
距离矩阵可以表示有效的加权有向图，也可以不表示。如何检查它是否表示有效的加权有向图？
浏览 0提问于2019-04-27得票数 0
如何在2D矩阵中找到从左上角到右下角的最小路径，计算成本，我们可以从北、南、东、西方向穿越。
浏览 3提问于2016-07-06得票数 1
回答已采纳
1回答
我有一个问题，我真的在努力解决。我有一组带有权重边的村庄，我需要创建一棵最小生成树来寻找最短路径，我已经根据权重找到了村庄的最短路径，我真的不知道该怎么做，我如何才能用邻接矩阵实现这一点？我将非常感谢您的帮助:)
-10个村(节点)
浏览 0提问于2013-12-12得票数 2
我正在研究Dijkstra的算法，我真的需要找到所有可能的最短路径，而不仅仅是一条。我使用邻接矩阵，并应用了Dijkstra算法，我可以找到最短路径。但我需要以最小的成本找到所有的路径，我是说所有可能的解决方案，如果它们存在的话。
这是我的算法是如何工作的，对于一个单一的解决方案：
public void dijkstra( int graph[][] )
{
int d[] = new int[ graph.length ];
int dC[] = new int[ graph.length ];
int p[] = new int[ graph.length ];
浏览 1提问于2010-05-12得票数 16
1回答
我被困在这个问题上：
假设我们在字母表{0，X，Y}上有以下m by n网格配置(或矩阵) G
G=
0 0 X .X
0 0 X .0
X，Y0 .X
：
0×0 .0
找到一个好的下限，其中<代码>E 128</代码>Y</代码>E 229</代码>可以移动<代码>E 130</代码>左<<代码>E 231</代码>、<代码>E 132</代码>右<//代码>、<代码>E 134</代码>up<code>E 235/
浏览 2提问于2016-04-01得票数 2
只接受普通向量作为输入。但我只有一个距离矩阵。还有其他Python模块来处理这个问题吗？
浏览 2提问于2016-02-26得票数 0
回答已采纳
3回答
有没有一种图算法，在给定起点(V)和终点(U)的情况下，可以找到通过给定的一组边的最短路径，但如果u是不连接的顶点，它还会确定添加缺失边的最短路径，直到u不再断开为止？
我有一个像素矩阵，其中的线条由255(黑色)和0(白色)组成。行(255)可以有中断或短路，我必须将两者都去掉。我可以有一个像素矩阵森林，比如说7棵左右的黑色像素树。我需要找到每棵树的真实端点，找到每棵树的最短路径，然后将所有倾斜树合并在一起形成一条线(即从原始矩阵中最远的两个端点开始的一条最短路径)。所有边权重都可以视为1。
谢谢
浏览 3提问于2009-08-23得票数 1
1回答
假设我们在一个无向循环加权图中有一条路径。假设我们有一个引擎可以在这样的图中找到从节点A到节点B的路径，有没有一种简单的方法/算法来计算出从A到B的给定路径是否比从A到B的任何其他不相交的路径至少好X%？我所说的不相交是指两条路径不能共享任何边。
浏览 1提问于2011-10-08得票数 1
回答已采纳
3回答
我看过类似的问题，这些问题详细介绍了Maps的排序和原始数据类型数组的排序，但没有任何问题直接详细说明了Java Map的一次排序与原始数据类型数组([])之间的区别。
Primary note*我知道' TreeMap‘是Java的排序版本(按键排列)，但我不知道TreeMap如何对键排序的“幕后”(在添加数据时，还是在数据被添加之后)？
Primary note 2* Dijkstra的算法in this case不是一个精确的实现。我们只是在M节点的图G中找到加权边的最短路径。这意味着邻接矩阵(如下图所示)大小为M.，这是not，一个智能实现。就像你能得到的底线一样.抱歉弄乱了！
浏览 2提问于2013-04-10得票数 1
回答已采纳
1回答
我正在寻找python代码帮助查找源到目的地之间的距离。函数的输入将是行数、列数和区域，即行数X列矩阵。
我们可以向上、向下、左边或右边一次遍历一个细胞。
可访问区域由1、无法访问的0和目的地9表示。
样本输入
numRows=3
numCols=3
alist=[[1,0,0],[1,0,0],[1,9,1]]
输出:应该是表示到目标的总距离的整数，如果没有路径，则为-1。
对于示例输入，遍历的路径将是(0,0)->(1,0)->(2,0)->(2,1)，函数应该返回和输出3
这里是我可以得到的伪代码，但需要帮助找出完整的解决方案。
def findthep
浏览 1提问于2018-09-17得票数 0
2回答
如果有一个4*2矩阵:A= 1,2;3,4;5,6;7,1，我需要找到在这些行之间至少有一个公共元素的行。例如，在上面的示例中，第1行和第4行有1个共同之处。该矩阵行可以具有很大的长度。最好的算法/逻辑是什么？
我尝试了以下算法：
for(i=0;i<N;i++){
for(j=i+1;j<N;j++){
if(ipArr[i][0] == ipArr[j][0] || ipArr[i][0] == ipArr[j][1] ||
ipArr[i][1] == ipArr[j][0] || ipArr[i][1] == ipArr[j][
浏览 1提问于2017-02-17得票数 3
1回答
只要想一想下面的一个算法就可以了。
给定一个矩阵，每个节点都有一个值。您从0,0开始，并且必须到达n,m。在i,j中，您可以转到i+1,j或i,j+1。当您踩到每个块时，该块上的值将添加到您的当前分数中。你必须携带的最低初始分数是多少，这样你才能始终到达n,m(通过任何可能的路径)，并在结束时获得正分数。
例如：
Matrix -> 2 3 4
-5 -6 7
8 3 1
Ans -> 6-对于路径2、-5、-6、3、1，我们需要初始分数为6，这样当我们到达1时，我们的正分数为1
浏览 0提问于2016-04-03得票数 1
本质上，我有一个浮子矩阵，范围从0到1，我需要找到最小和的值的组合。问题是，一旦选择了一个值，就不能使用该行或列中的其他值。必须使用所有列。
在矩阵宽度大于高度的情况下，用1填充矩阵，使矩阵正方形。在高度大于宽度的情况下，并不是所有的行都会被使用，但是必须始终使用所有的列。
我已经研究过二叉树和Dijkstra的算法来完成这个任务，但是对于较大的矩阵，两者似乎都变得太复杂了。理想情况下，我正在寻找一个算法或实现，它将在相对较短的时间内提供一个很好的猜测。任何为c++优化的东西都会很棒！
浏览 3提问于2017-04-05得票数 1
回答已采纳
2回答
全,
我正在阅读关于所有对、最短路径和矩阵乘法之间的关系。
考虑了加权邻接矩阵本身的乘法，但在这种情况下，我们用加法代替矩阵乘法运算，用极小化代替加法运算。注意，加权邻接矩阵本身的乘积返回一个矩阵，该矩阵包含任意一对节点之间长度为2的最短路径。
由此得出的结论是，A到n的幂包含所有最短路径。
问题1：
我的问题是，在一个图中，在一个路径中的两个节点之间最多有一个n-1边，作者在什么基础上讨论了长度"n“的路径？
以下幻灯片
在幻灯片10中，如下所示。
dij(1) = cij
dij(m) = min (dij(m-1), min1≤k≤n {dik(m-1) + ckj}) -
浏览 7提问于2011-12-05得票数 3
回答已采纳
3回答
全对最短路径，领带断裂
、、、
我正在创建一个程序，它将计算未加权图中所有节点的Betwenness中心性。要做到这一点，我必须找到ASSSP (所有单一源最短路径)。在创建程序时，我意识到最终我将有联系(从源到目的地的距离相同，但路径不同)。这使我想到了这个问题。我该如何解决这些关系？如果我使用随机的断线器，那么对于相同的输入，中间中心度的每个输出可能略有不同。让我做一个小小的示范性图：
A
/ \
B C
\ /
D
现在假设A节点是我们希望找到ASSSP的源。可见，有两条路径(A->B->D和A->C->D)，bot的长度相同，两者最短。现在我应该选择哪一个，在什么条件
浏览 2提问于2012-07-11得票数 2
回答已采纳
1回答
给出了一个维数的代价矩阵m×n.The问题，就是求出从左上角到matrix.The中某个单元格的最小路径。路径的总成本是path.Only 2移动中访问的所有单元的总成本之和:要么下降一行，要么向右移动一列。你不能在任何时候离开矩阵，其中一些细胞被标记为障碍，不能被踩上。表中的几个问题: tx将被回答。该查询的输出应该是从左上角到tx行约束中ty列索引的路径的kth最小成本：
1<= m,n <= 100 0 <= tx < m 0 <= ty <n 1 <= k <= 101
The obstacles in matrix are marke
浏览 3提问于2014-08-30得票数 0
回答已采纳
我目前正在研究Bellman算法，出现了一个疑问。据我所知，Bellman算法从它的来源创建最短路径，如果图中有一个负循环，它返回true，算法停止，另一方面，它用最短路径返回false。
我现在的问题是，该算法是避免了图中创建最短路径的正循环，还是没有考虑到它们(因而落入了它们的陷阱)？
提前感谢！
浏览 4提问于2022-01-12得票数 1
回答已采纳
3回答
我很难理解的用处。我认为这个问题对于一个在这个领域有知识的人来说听起来一定很愚蠢，但我想不出来。根据维基百科，Johnson算法使用Bellman Ford算法将边的权重转换为非负权重，然后使用Dijkstra算法查找最短路径。但贝尔曼·福特算法也是一种寻找最短路径的算法。为什么我们不使用从贝尔曼·福特算法得到的最短路径呢？
浏览 0提问于2011-03-16得票数 4
回答已采纳
2回答
我不确定我在这里是否使用了正确的术语。我试图想出一个算法，让我们在任意图中找到一个顶点，这样顶点与最远顶点的距离最小。
另外，我还想出一个算法，让我找到两个顶点，而不是一个，再把最远的顶点到这两个顶点之间的距离最小化。
我的直觉说，我应该想出一个算法，计算出图中所有顶点之间的最短路径，然后查看路径，找到流量最高的顶点。但是我很难想出一个具体的算法，因为我以前根本没有这方面的经验。我试着用谷歌搜索这个问题，但没有成功。如有任何指导，将不胜感激。
浏览 0提问于2016-11-01得票数 -2
回答已采纳
1回答
我正在看。
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
// part 1
for each vertex v
dist[v][v] ← 0
// part 2
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
// part 3
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
浏览 2提问于2013-06-03得票数 0
回答已采纳
我目前正在研究非负边权图中的最短路径问题。
我知道Dijkstra算法可以给出单源最短路径问题的解决方案，也就是可以找到从一个节点到所有其他节点的最短路径，但是我还没有找到算法，可以给我一个先验的更简单的问题:找到两个节点之间的最短路径。
直觉上，我认为可以找到例子，表明“简单”问题并不比单源最短路径问题更简单，但我正在寻找参考资料，在简单的图(即有几个节点)上显示这种矛盾(先验)。
浏览 4提问于2022-05-11得票数 2
1回答
如何在图或ANN中引导信息流？
、、、、
我正在构建一个无方向的ANN。没有不同的输入或输出节点，并且所有连接都是无定向的。
为了使网络工作，我正在设计系统，将每个节点的动作阈值和加权关系视为其到“焦点”节点(临时输出节点)的距离的函数。
换句话说，我将任意选择一个或一组节点作为数据的端点和输出。此节点可以随时更改。流经图形的信息流将像磁铁一样吸引所选节点，因为从统计上讲，靠近末端节点的节点更有可能激活并沿该路径发送信息。
我希望这可以创建一个非常动态和现实的ANN模式，具有非常准确的学习模式。
现在，我被困在如何有效地确定每个节点到末端节点的距离的问题上。据我所知，如果我使用Neo4j，平均需要大约250ms来计算两点之间的最短路径
浏览 0提问于2011-07-30得票数 2
回答已采纳
1回答
是否可以使用Dijkstra's Algorithm计算从单个源到单个目标的N条最短路径，其中N是节点数？我知道Dijkstra从一个源输出到图中所有节点的最短路径，但当我正在读一篇研究论文时，作者提到了使用Dijkstra计算s和t之间的N条最短路径，这让我有点困惑。
以下引用原文：利用基于SDN的SCADA系统:一个反窃听的案例研究-也发现了
Dijkstra的算法22用于计算N个阶段的最短路径(步骤5)。考虑N= 2，在第一阶段，Dijkstra算法确定了两个网络设备之间最短的路由，从而使所有链路开销的权重增加了10倍。紧接着，在第二阶段(并且随着链路成本的增加)，Dijkst
浏览 0提问于2015-11-25得票数 2
回答已采纳
2回答
我试图研究平面上两点之间的短路径的不同算法。
我发现的绝大多数算法使用离散映射(网格映射、可见性图、Voronoi路线图等)。
有些书(如Ben的“机器人元素”或Nikolaus的“自主机器人简介”)提到了连续地图(例如原始多边形数据)，但没有解释相应的算法。他们声称记忆或效率优势的少数和简单的障碍，这可能是非常有趣的。
我认为，应该有一个聪明的方法，使用几何计算(例如，交叉检测)和一些算法范式(例如，最小成本分支和界)，但我不想糟糕地重新发明车轮。
是否有任何资源用于使用连续映射或有用的关键字来搜索短路径算法？
像建议的那样，我试图指定我使用的一些术语：
连续映射
指
浏览 6提问于2020-08-19得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
