带顶点权的图最短路径
以下是消费税：
在某些图的问题中，顶点可以有权代替边的权或增加边的权。设Cv是顶点v的代价，C(x，y)是边(x，y)的代价。该问题涉及到在图G中寻找顶点a和顶点b之间的最便宜路径，路径的代价是该路径上遇到的边和顶点的代价之和。
(a)假设图中每条边的权重为零（而非边的代价为∞)，假设所有顶点1≤V≤n（即所有顶点的代价相同），Cv=1。给出一个求从a到b最便宜路径的高效算法及其时间复杂度。
(b)现在假设顶点成本不是常数（而是全部为正），边成本保持如上。给出一个求从a到b最便宜路径的高效算法及其时间复杂度。
(c)现在假设边和顶点代价都不是常数（但都是正的）。给出一个求从a到b最便宜路径的高效算法及其时间复杂度。
(c)
也使用Dijkstra算法
如果只考虑边缘权，那么对于Dijkstra算法的关键部分，我们有：
if (distance[y] > distance[v]+weight) {
distance[y] = distance[v]+weight; // weight is between v and y
}
if (distance[y] > distance[v] + weight + vertexWeight[y]) {
distance[y] = distance[v] + weight + vertexWeight[y]; // weight is between v and y
}
共有1个答案
你已经走上了正确的轨道，解决方法很简单。
在B、C中，将问题归结为正规dijkstra问题，它假定顶点上没有权。
为此，您需要定义w':e->r，这是一个新的边权重函数。
w'(u,v) = w(u,v) + vertex_weight(v)
在(b)w(u，v)=0（或const）中，并且该解对拟合(c)也是稳健的！
（1）在此解决方案中，您“错过”了源的权重，因此从s到t的最短路径将是:Dijkstra(s,t,w')+vertex_weight(s)_[其中Dijkstra(s,t,w')是从s到t使用W'的距离
-
我们有一个边带正权的有向图G(V，E)，作为源顶点s，目标点T。此外，最短的s-t路径包括图中的每一个其他顶点。我需要计算s和t之间的交替最短路径距离，以防某些边e∈e被删除。我想设计一个O(e^2logV)算法，它计算图G\e中所有e∈e的最短S-T路径距离。最后的输出应该是一个大小为E的数组，其中edge E的条目应该包含G\E中最短的S-T路径距离。
-
在无向赋权图中寻找两个顶点之间的最短路径。还已知权重是小于log（logV）的整数，其中V是顶点的数量。使用贝尔曼-福特或Dijkstra算法很容易解决，但是有没有什么算法可以更快地解决呢？ 到目前为止，我一直在考虑使用BFS，将权重大于1的边划分成两个权重为1的边，但如果V是大数，就不是一个好主意。不，这不是我的家庭作业，我只是在想。
-
我试图弄清楚，如何计算具有加权顶点的图的最短路径。经典算法，如Dijkstra和Floyd-WarMarshall，通常使用加权边，我看不到如何将它们应用于我的情况（加权顶点）： 我的一个想法是将图形转换为带有加权边的更经典的视图。这是我收到的： 这里我们有单向和双向加权边，但我仍然不确定哪种算法可以处理这一点，以找到最短路径。
-
我有一张室内地图上的无向位置图。当给定一组顶点时，我要找到覆盖所有这些顶点的最短路径。图形包含52个顶点和150-250条边。 我能用什么最好的算法来找到最短的路径。请不要混淆这是一个旅行推销员的问题。它不需要覆盖所有节点，只需要覆盖给定的节点集。
-
给定一些无向边加权图，什么算法可以用来找到从某个顶点v到另一个顶点w的最短路径？ 对于有向边加权图，可以使用Dijkstra的最短路径算法，但我使用的是无向图，所以它不起作用。 对于非边加权的图，可以使用广度优先搜索（BFS），但我使用的是边加权图，所以它不起作用。 既然它是无向和边加权的，一般最短路径法是什么？
-
然而，出现的问题是，当我将一个顶点设置为一个旅游站点并给它一个权重时，该顶点在第一次访问时似乎根本没有权重。然后，当第二次访问顶点时，权重显示出来。我不知道问题出在哪里，但我猜是因为我没有直接编辑原始变量。 打印输出行标记在下面的**之间。一个在calculateShortest（）中，另一个在calculateMin（）中。 显示问题的行打印输出（不包括main方法输出）：