4回答
“弗洛伊德-沃尔”算法“和”Dijkstra的算法“”之间有什么区别，哪种算法是图中最短路径的最佳选择？
我需要计算网络中所有对之间的最短路径，并将结果保存到一个数组中，如下所示：
**A B C D E**
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
浏览 20提问于2009-12-04得票数 27
回答已采纳
我有一个项目涉及到用机器人的手绘图，它只能在x，y坐标上移动。对于给定的二进制图像，我已经使用DFS来探索它。DFS算法返回DFS探索过的一系列点。那个数组就是路径。效果很好。
问题是该路径中存在跳转( DFS算法返回带跳转的路径)。例如：
00000000000
00001000000
00001000000
01111000000
00001000000
00001000000
00000000000
DFS返回的路径如预期的那样：(3,1)->(3,2)->(3,3)->(3,4)->(2,4)->(1,4)->(4,4)->(5,4) --我的
浏览 0提问于2017-08-02得票数 0
我不知道这个问题的名称，所以还没有真正研究它。我有一个完整的加权图，有一个开始和结束节点和n个不同的节点集(让我们称它们为红色、蓝色和绿色)，每个节点都有m个成员节点。
我需要找到从头到尾的最短路径，必须经过一个红色、一个蓝色和一个绿色节点；有算法吗？
扩展将是，我需要找到最短的路径访问时，首先是蓝色，然后绿色，然后红色(再次，准确地每一次)；这有一个吗？
浏览 2提问于2016-10-06得票数 3
回答已采纳
1回答
使用限制提升c++ Astar
、、、、
我使用的是boost 的astar算法
我想为从起始节点到目标节点的路径长度积分一个长度条件。更具体地说，我试图找到一个精确长度为11位的数字链。一个想法可能是集成到boost A*实现的访问者模式中。但到目前为止，我还没有找到好的解决方案。
更一般的是，我正在寻找一种方法，将语法检查集成到A*算法中。在我的具体例子中，语法可以用一个规则模式来表示，比如^1-9\d{10}$每个节点代表一个字符(这里是一个数字)。任何建议都是值得感谢的。
浏览 2提问于2017-12-27得票数 0
我面临着在矩阵中寻找起点和终点1之间的最短路径的问题。
例如：
------------
3 | 44 | 75 |
------------
21 | 98 | 60 |
-------------
each中的值表示跨越每个point.You所需的成本，每个单元格可以移动到其右边的单元格，或者不允许移动到it.Diagonal下面的单元格。
我应该像BFS，dijkstra一样使用哪种算法？
1)
package com.oft.controller;
import java.util.Iterator;
import java.util.List;
import javax.se
浏览 0提问于2014-05-29得票数 0
2回答
用A*算法求几条最短路径
、、、
我正在制作一个路由应用程序，它使用A*算法来查找路由。我想提供的不只是一条路线，还有几条替代路线。例如，仅比最佳路由稍长一点的路由。
由于A* (和其他许多)只找到一条路线，我如何搜索这些替代路线？我应该使用其他算法吗？
浏览 0提问于2015-02-26得票数 1
2回答
给出了一个有向图，其中每个边都有一个cost.Taking优点，即图中最多有两个负边，我的目标是求出从给定节点到V中所有节点的最短路径距离。算法的时间复杂度应该是O(|E| + |V|*log|V|)，所以我认为需要应用Dijkstra算法。
我猜想我需要以某种方式将我给定的图转换成一个新的图，该图中从s到v的最短路径将等价于给定图中所需的最短路径。或者我需要修改Dijkstra的算法？
我现在很挣扎。任何帮助都将不胜感激！
浏览 4提问于2014-02-04得票数 0
回答已采纳
1回答
假设我们在一个无向循环加权图中有一条路径。假设我们有一个引擎可以在这样的图中找到从节点A到节点B的路径，有没有一种简单的方法/算法来计算出从A到B的给定路径是否比从A到B的任何其他不相交的路径至少好X%？我所说的不相交是指两条路径不能共享任何边。
浏览 1提问于2011-10-08得票数 1
回答已采纳
3回答
有没有人知道在PHP中是否有一种简单的路径查找方法？
我基本上有一个数字列表。
{origin:11485,outboundDirections:"11486,11487,11488"}
{origin:11487,outboundDirections:"11485,11676,94185"}
从11485到94185将导致11485>11487>94185以“退出”的方式出现，我正在努力弄清楚如何做到这一点(这真的不需要是最短的路径或任何类似于人工智能的方式，只是从A到B的一种方式)。
不幸的是，我根本不知道从哪里开始
浏览 10提问于2011-01-05得票数 2
回答已采纳
2回答
我有一个带有n顶点的加权无向图G。其中两个顶点是X和Y。
我需要找到一条最短的路径，它从X开始，在Y结束，经过G的所有顶点(以任何顺序)。
我怎么能做到这一点？
这不是旅行商问题:我不需要访问每个顶点一次，我也不想回到第一个顶点。
浏览 0提问于2016-04-16得票数 6
我最近正在学习图形算法，在我的大学里，我们被教导说，Bellman的结果是一个从所有节点到所有其他节点的距离表(所有对最短路径)。然而，我不明白这个算法是如何实现的，我试图通过观看YouTube视频和查找维基百科中的定义来理解它……
现在问题来了：
我无法找到描述该算法的资源，其结果将是所有对最短路径表，但只能“从一个节点到所有其他节点”。
对Bellman算法进行调整以实现所有对最短路径表，还是我的大学讲师在这方面完全错了？(他解释了一些提供所有对最短路径的算法，他称之为Bellman，但我认为这不可能是Bellman)。
编辑:我绝对理解Bellman算法中的“从一个节点到所有其他节点的最
浏览 8提问于2017-07-16得票数 1
回答已采纳
2回答
贾尼克斯特拉最短路径算法
、、、、
我正在学习different的代码，我已经准备了下面的代码，所依据的是与different略有不同的想法。现在，在许多网站上，我看到了使用提取min和布尔数组访问的边缘。我没有用过，我的答案也是正确的。是否有任何测试用例或场景让我的algo无法工作。
import java.util.*;
class ShortestPath2 {
static int Ar[][];
static int dist[];
static int nodes;
public static void djikstra(int sou
浏览 1提问于2016-09-30得票数 0
回答已采纳
1回答
我目前正在为我的一次考试做修改，我已经回答了这个问题，“逐步显示，使用Dijkstra的算法在图中找到从顶点A到彼此顶点的最短路径。在每一步，已知的和边界的集合都应该清楚地显示出来。”我知道如何找到最短的路径，但我确信什么是边框集？谢谢!
浏览 1提问于2017-05-04得票数 2
回答已采纳
3回答
全对最短路径，领带断裂
、、、
我正在创建一个程序，它将计算未加权图中所有节点的Betwenness中心性。要做到这一点，我必须找到ASSSP (所有单一源最短路径)。在创建程序时，我意识到最终我将有联系(从源到目的地的距离相同，但路径不同)。这使我想到了这个问题。我该如何解决这些关系？如果我使用随机的断线器，那么对于相同的输入，中间中心度的每个输出可能略有不同。让我做一个小小的示范性图：
A
/ \
B C
\ /
D
现在假设A节点是我们希望找到ASSSP的源。可见，有两条路径(A->B->D和A->C->D)，bot的长度相同，两者最短。现在我应该选择哪一个，在什么条件
浏览 2提问于2012-07-11得票数 2
回答已采纳
1回答
Dijkstra算法伪码
、、、、
我正在尝试用C++编写Dijkstra算法，在互联网上有无数的例子，但我似乎就是不能掌握这些例子是如何工作的。我更愿意以一种对我有意义的方式来做，这样我就可以更好地理解算法。我知道算法本身应该如何工作，并且我已经写了一些代码。我想知道是否有人能指出我思维过程中的缺陷。我选择将我的图表示为边列表。我将用伪代码编写，因为我的实际代码是一个巨大的混乱：
class Node{
vector<node> linkVector; //links to other nodes, generated at random
int cost;
浏览 0提问于2013-04-18得票数 1
回答已采纳
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
回答已采纳
我目前正在研究Bellman算法，出现了一个疑问。据我所知，Bellman算法从它的来源创建最短路径，如果图中有一个负循环，它返回true，算法停止，另一方面，它用最短路径返回false。
我现在的问题是，该算法是避免了图中创建最短路径的正循环，还是没有考虑到它们(因而落入了它们的陷阱)？
提前感谢！
浏览 4提问于2022-01-12得票数 1
回答已采纳
3回答
我很难理解的用处。我认为这个问题对于一个在这个领域有知识的人来说听起来一定很愚蠢，但我想不出来。根据维基百科，Johnson算法使用Bellman Ford算法将边的权重转换为非负权重，然后使用Dijkstra算法查找最短路径。但贝尔曼·福特算法也是一种寻找最短路径的算法。为什么我们不使用从贝尔曼·福特算法得到的最短路径呢？
浏览 0提问于2011-03-16得票数 4
回答已采纳
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
回答已采纳
2回答
我不确定我在这里是否使用了正确的术语。我试图想出一个算法，让我们在任意图中找到一个顶点，这样顶点与最远顶点的距离最小。
另外，我还想出一个算法，让我找到两个顶点，而不是一个，再把最远的顶点到这两个顶点之间的距离最小化。
我的直觉说，我应该想出一个算法，计算出图中所有顶点之间的最短路径，然后查看路径，找到流量最高的顶点。但是我很难想出一个具体的算法，因为我以前根本没有这方面的经验。我试着用谷歌搜索这个问题，但没有成功。如有任何指导，将不胜感激。
浏览 0提问于2016-11-01得票数 -2
回答已采纳
我目前正在研究非负边权图中的最短路径问题。
我知道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
回答已采纳
如何使用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回答
我的理解是，BFS和DFS是图遍历算法，而其他算法(如A*和dijkstra )则用于在图的两个节点之间寻找最短路径。但是在一些地方，我认为BFS和DFS也被称为最短路径查找算法。请详细说明图遍历算法与最短路径查找算法的区别。谢谢!
浏览 6提问于2022-05-06得票数 0
在最近的一次采访中，我被要求实现单源最短路径算法(对于无向和正加权图)，即给出一个额外的边，其权重'w‘。我们必须找到一条比SSSP algo计算的更短的路径，方法是将两个尚未连接的节点之间的额外边连接起来，并加上权重'w‘。
但考虑到额外的优势。它可以连接在A和D之间，而D和A之间还没有连接，从而使通过SSSP algo产生的最短路径最小化。
我试着考虑解决办法。但到目前为止什么都没有发生。我已经实现了Dijkstra算法来找到最短路径。但这个小小的改动让我很困惑。你能帮点忙吗。
浏览 4提问于2016-10-17得票数 3
回答已采纳
2回答
我想知道是否有一种算法可以在图中找到最短路径。
假设我有一个图，从一个顶点到另一个顶点有一对路径。这些路径中的两条或更多条具有相同的成本。如何标记、查找这些顶点之间的所有最短路径？据我所知，Dijkstra或Bellman-Ford算法会找到最短路径，但他们只“选择”一条。
浏览 1提问于2010-08-09得票数 1
回答已采纳
Shortest Path算法与Djikstras Algorithm算法和Travelling Salesman算法有什么区别？据我所知，在Shortest Path中，我们不会通过所有最短路径的顶点。在Travelling Salesman Problem中，我们只遍历所有顶点一次。关于Djikstra's Algorithm，我学到的和旅行的推销员是一样的。但视频教程()却有不同之处。
请解释一下。
浏览 8提问于2014-10-16得票数 1
回答已采纳
给定一个有向加权图(没有负边)，从一个节点到另一个节点的最短距离是多少，并且满足从一个节点/顶点到另一个节点/顶点的“跳数”必须小于某个特定值k的条件。(其中k肯定小于节点的数量)。
一个“跳”被定义为从一个节点移动到另一个节点，并且“跳”值从源节点从1开始。
这个问题并不像简单地运行Dijkstra算法那么简单，因为这个算法只给出了最短的距离，而没有考虑“跳数”。
考虑1:从源节点到端节点的最短路径可能超过允许的最大跳数。
考虑2:增加Dijkstra算法以最小化“跳数”将给你一个可能的答案，但它可能不是最短的。
请注意，这里的优先事项仍然是最小化最短距离，只是有了一个新的条件，即“跳数”需
浏览 2提问于2019-03-29得票数 1
1回答
每个人都知道饼干桶三角形钉纸牌游戏。你拿着一个钉子，跳到另一个洞里，目标是只剩下一个钉子。
在我的游戏板对象的代码中，我有一个sCpeg(int a, int b)函数，它可以更改您当前用于跳转的peg。我将它连接到一个moves变量来解决它。每次你改变当前的钉子并使用它来跳跃，这就算一次移动。这是一个非常基本的启发式方法，我希望它是一个搜索算法:用一个peg探索所有可能的跳转。如果未找到解决方案，请回溯，更新当前peg并重复此过程。
当我写出这个想法时，它听起来像是一个使用递归的完美例子，除了我不知道如何在这个场景中正确地使用递归。在回溯和更新当前的peg之间，我迷失了方向。
这一切听起来是
浏览 1提问于2015-04-20得票数 2
1回答
我有一个三角形矩阵NxN表示顶点之间的距离(顶点我只与向量j>i连接)，我想从第一个到最后一个对路径进行采样，并使用它作为训练样本。有算法来做吗？在A*中交换min->样品是否足够？
浏览 0提问于2020-01-13得票数 2
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
1回答
我需要在下面的图中计算从A到B的两条路径，约束条件是这些路径不能共享任何边：
嗯，好吧，不能上传图片，这是个。
所有的边都有正权重；对于这个例子，我认为我们可以假设它们是相等的。我的简单方法是使用Djikstra的算法来计算第一条路径，如上图中的第二张图所示。
然后，我从图中删除边，并尝试计算第二条路径，但失败了。有没有Djikstra，Bellman-Ford (或其他任何东西)的变体，可以计算上面第三张图中显示的路径？(我的意思是，不需要特殊知识，也不需要删除转载链接)
浏览 0提问于2010-05-11得票数 0
我想找一个图中2个顶点之间的下一条最短路径，并且这条路径有一个正的cost.The，下一条最短路径是允许共享边的最短路径，我可以使用.Which算法吗？
浏览 0提问于2011-02-12得票数 20
回答已采纳
1回答
我刚学过图论，需要一点帮助。假设我们有一个具有定义的开始和结束版本的图。如何使用BFS只得到起点和终点之间的最短路径。
我已经编写了一个计算整个图中最短路径的程序，但是当我想要将树限制在起始端之间的这些顶点时，我不知道如何实现它。
任何帮助，伪代码，建议将不胜感激。
浏览 8提问于2013-12-23得票数 1
回答已采纳
给出了具有n顶点和m弧(n <1 500，m<5 000)和一弧(u，v)的有向加权图.回答的问题是，有多少条最短路径(可以从a的任意位置开始，以b结束，以便a！= b)通过给定的弧。
示例：
N= 4，m=4
弧(1，2)的重量为5
弧(2，3)的重量为5
弧(3，4)的重量为5
弧(1，4)，重量为8
和弧(1，2)。
答案是2，因为弧(1，2)在最短路径1->3和1->2。
迪克斯特拉能解决这个问题吗？
浏览 1提问于2018-10-26得票数 3
我不是要求一个算法来检查图中负圈的存在(Bellman Ford或Floyd Warshall可以这样做)，而是在图包含至少一个从源顶点可以到达的负圈，并且从负圈可以到达目标顶点的情况下，是否存在多项式时间算法来寻找两点之间的最短路径。
浏览 3提问于2013-09-02得票数 2
回答已采纳
3回答
启发式算法是如何工作的？
、、、
最近我正在学习一些启发式算法，比如A*搜索算法。我知道一些关于启发式搜索算法的基本事实，如f(n)=g(n)+h(n)，我也知道每种方法的可容许性和一致性。但让我困惑的是启发式算法是如何工作的？如果启发式值更接近成本的实际值，为什么会更好？谢谢!
浏览 8提问于2013-10-07得票数 0
回答已采纳
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
2回答
我使用netwrokx计算不同顶点之间的最短路径，使用Dijkstra算法。我有一个例子，我想连接三个不同的顶点(例如，A，B和C在一个无向图中)。首先，我找到了从A到B的最短路径，然后我想要找到从A到B的路径的最短路径。到目前为止，我尝试的是从A到B路径的所有节点到C的最短路径长度，然后计算出从节点到给定最小路径长度的最短路径。这是计算密集型的，因为路径可能有多达200到300个节点。
有人能给我一个提示吗?我如何改进方法？或者更容易找到从已有的边缘到目标的最短路径？
浏览 1提问于2018-08-15得票数 2
回答已采纳
1回答
我有一个像加权迷宫一样的网格，我需要在没有任何关于迷宫的先验知识的情况下找到通向实体的最短路径。
像A* expect priot knowledge这样的算法在环顾四周时会“跳来跳去”，但当我有一个机器人的时候，这是不可能的。
我的第一个想法是最初使用BFS探索整个迷宫，然后在探索的迷宫上应用A*，以找到考虑权重的最短迷宫。但这似乎太天真了。
有没有人能给我一些适合这个问题的算法？
浏览 0提问于2018-12-10得票数 3
嗨，我在为这个问题而挣扎。其内容如下：
设计一种算法，在加权有向图G= (V，E)中求最小权环(即图中所有圈的最小边权和)。简要说明运行时和空间的复杂性。假设所有的边都是非负的。它应该在O时间内运行。提示:对Dijkstra的算法使用多次调用。
我已经看到了使用弗洛伊德-沃尔的解决方案，但我想知道我们将如何使用Dijkstra，以及如何在给定的时间限制内做到这一点。
我有几点困惑：
首先，我们如何知道图中有多少圈，以及如何检查这些循环？
还有，为什么会是E_？根据我的理解，你应该遍历所有的顶点，因此使它成为？
这是为了我的个人学习，所以，如果任何人有他们可以使用的例子，
浏览 4提问于2017-11-26得票数 0
我正在开发一个个人项目。在这个视频游戏中有一个基于网格的移动、创建和寻路系统。在此之前，我曾使用A*寻路来使某些字符移动到某个已知位置。
但现在我遇到了一个大问题。在我的游戏中有一个角色必须去一个特定的对象，但是这个角色不知道这个物体的精确坐标。最简单的方法是真正知道这些物体的坐标，计算出哪个是最近的，并使用A*路径查找来达到这个点，但是这种方法看起来确实是被操纵的，而且对我所做的游戏的类型来说还不够动态。
因此，我想知道是否有一些路径查找算法可以在某个点(正在使用该算法的字符的位置)附近搜索，比如以径向方式进行搜索，并一直搜索直到它找到正在寻找并返回到该特定对象的路径的对象类型。
浏览 7提问于2016-06-01得票数 0
回答已采纳
2回答
Dijkstra的最短路径算法会在具有负权边的有向树上返回正确的结果吗？
在具有负权重的一般图上，该算法将失败，但由于它是一棵有向树，因此感觉该算法会成功。
浏览 5提问于2022-06-01得票数 2
1回答
改进Dijkstra算法
、、、、
给出了一个边权W介于0~ 1之间的有向图。从源到目标节点的路径代价是路径上从源到目标节点的边权的乘积。我想知道一种算法，它可以在多项式时间内或使用任何其他启发式方法找到最小代价路径。
我认为沿着取边权的对数值(取模值)，然后对这个图应用dijkstra，但认为会有无法计算的精度问题。
还有其他更好的方法吗?或者我可以改进日志方法。
浏览 0提问于2016-11-07得票数 1
1回答
图算法问题给你。
我有一个图表，用来表示一个道路网络。因此，在它的循环(一个回旋将是一个微不足道的)。还有一些边缘是双向的，有些是单向的(单向街道).边是按长度加权的。
假设我有两个节点，并且已经计算了它们之间的最短路径。我想要做的是找到连接两个节点的所有其他路径，它们都比某个距离还要短。
下面是ascii技术中的一个例子，其中我用字母标记了边，用数字标记了节点。
F
5----6
E / \ G
3--------4
/ D \
B / \ C
1--------------2
浏览 3提问于2013-09-07得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
