Dijkstra算法的修改

Question

我想知道，当给出起始顶点s时，只有当顶点距离起始顶点不超过三个边时才计算最短路径。

我想通过计算父母的数量来做到这一点，如果number_of_parents < = 3那么它是一个有效的路径。

请有人可以澄清这一点对我来说，使用算法？

下面是标准的Dijkstra算法。

Dijkstra(G,W,s) 
    Initialize_Single_Source(G,s) 
    S= {} 
    Q = V[G] 
    while Q != {} do 
     u = extract_min(Q) 
     S = S U {u} 
     for each vertex v element of Adj[u] do 
       relax(u,v,w) 

Answer 1

而不是一个顶点，我们用排列L确定水平，即节点相差多少

Dijkstra(G,W, s) 
    Initialize_Single_Source(G,s) 
    S= {} 
    Q = V[G] 
    L = {an array to determine levels of each node, 
    initially all nodes have level "infinite" except for s who has level 0} 
    while Q != {} do 
     u = extract_min(Q) 
     u_level = L[u] 
     if(u_level > 3){ 
     ignore u and don't add it to S; 
     continue; 
     } 
     S = S U {u} 
     for each vertex v element of Adj[u] do 
       relax(u,v,w) 
       in relax function you put L[v] = min(L[v], u_level + 1);