设G是directed and unweighted图:G=(V,E)。我想从节点s,to all vertices with a multiple of 3 edges (arcs)找到最短的路径。
我的想法是构建新的图,G',它包括:为原始图中的每个节点复制3个副本,称为v1,v2,v3。对于原始图中的每个边(弧) (u,v),我将在新图中构建3条新的边:(u1,v2),(u2,v3),(u3,v1)。然后使用BFS算法来检查是否有从v1到u1的路径,然后它(可能吗?)告诉我们,有一条路径从s经过3条边的倍数。我不知道这是否解决问题的办法。有人能帮我解决这个问题吗?
public int dijkstra(){
boolean[] visited = new boolean[gSize];
int src = 1;
int dest = 1;
int[] distance = new int[5];
int[] part = new int[5];
int min;
int nextNode = 0;
for(int i = 0; i < 5; i++)
{
visited[i] = false;
part[i] = 0;
我有一个有向加权图,它的权重为正数,如下所示:
我想做的是:-
查找两个节点之间的所有可能路径。
根据路径长度(由边缘权重确定)按升序排列路径,至少前5位表示。
使用一种最优的方法来做到这一点,这样即使在节点数量更多的情况下,程序也不会花费太多的时间计算。
例如:-假设我的初始节点是d,最后一个节点是c。所以输出应该类似于
d to c = 11
d to e to c = 17
d to b to c = 25
d to b to a to c = 31
d to b to a to f to c = 38
我怎样才能做到这一点?
我正在寻找Dijkstra的算法实现,它也考虑了遍历的节点数量。
我的意思是,一个典型的Dijkstra算法,在计算从节点A到节点B的最短路径时,考虑了连接节点的边的权重。我想在其中插入另一个参数。我希望算法也能对遍历的节点数量赋予一定的权重。
因此,在某些值下,计算出的从A到B的最短路径可能不一定是最短路径,而是经过的节点数量最少的路径。
对此有什么想法吗?
干杯,
RD
编辑:
我很抱歉。我应该解释得更清楚些。所以,让我们假设,从
(A,B)是A -> C -> D -> E -> F -> B,共10个单元
但我希望算法能得出总共12个单元的路由A、->