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);