Dijkstra算法的修改

Question

我想知道，当给定起始顶点s时，仅当顶点距起始顶点不超过三条边时才计算最短路径。

我想通过计算parents的数量来做到这一点，如果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);

Dijkstra算法的修改

Modification for Dijkstra Algorithm

algorithm

dijkstra

shortest-path