{
  "id": "enwiki-001315062833",
  "slug": "parallel-single-source-shortest-path-algorithm",
  "title": "Parallel single-source shortest path algorithm",
  "qid": "",
  "lead": "A central problem in algorithmic graph theory is the shortest path problem. One of the generalizations of the shortest path problem is known as the single-source-shortest-paths (SSSP) problem, which consists of finding the shortest paths from a source vertex s to all other vertices in the graph. There are classical sequential algorithms which solve this problem, such as Dijkstra's algorithm. In this article, however, we present two parallel algorithms solving this problem. Another variation of the problem is the all-pairs-shortest-paths (APSP) problem, which also has parallel approaches: Parallel all-pairs shortest path algorithm.",
  "body": "A central problem in algorithmic graph theory is the shortest path problem. One of the generalizations of the shortest path problem is known as the single-source-shortest-paths (SSSP) problem, which consists of finding the shortest paths from a source vertex s to all other vertices in the graph. There are classical sequential algorithms which solve this problem, such as Dijkstra's algorithm. In this article, however, we present two parallel algorithms solving this problem. Another variation of the problem is the all-pairs-shortest-paths (APSP) problem, which also has parallel approaches: Parallel all-pairs shortest path algorithm. Let G=(V,E) be a directed graph with |V|=n nodes and |E|=m edges. Let s be a distinguished vertex (called \"source\") and c be a function assigning a non-negative real-valued weight to each edge. The goal of the single-source-shortest-paths problem is to compute, for every vertex v reachable from s , the weight of a minimum-weight path from s to v , denoted by \\operatorname{dist}(s,v) and abbreviated \\operatorname{dist}(v) . The weight of a path is the sum of the weights of its edges. We set \\operatorname{dist}(u,v):=\\infty if v is unreachable from u . Sequential shortest path algorithms commonly apply iterative labeling methods based on maintaining a tentative distance for all nodes; \\operatorname{tent}(v) is always \\infty or the weight of some path from s to v and hence an upper bound on \\operatorname{dist}(v) . Tentative distances are improved by performing edge relaxations, i.e., for an edge (v,w)\\in E the algorithm sets \\operatorname{tent}(w):=\\min\\{\\operatorname{tent}(w), \\operatorname{tent}(v)+c(v,w)\\} . For all parallel algorithms we will assume a PRAM model with concurrent reads and concurrent writes. The maximum shortest path weight for the source node s is defined as L(s):=\\max\\{\\operatorname{dist}(s,v) : \\operatorname{dist}(s,v) , abbreviated L . Also, the size of a path is defined to be the number of edges on the path. We distinguish light edges from heavy edges, where light edges have weight at most \\Delta and heavy edges have weight bigger than \\Delta . Following is the delta stepping algorithm in pseudocode: 1 foreach v \\in V do \\operatorname{tent}(v):=\\infty 2 relax(s, 0) ; (*Insert source node with distance 0*) 3 while \\lnot isEmpty(B) do (*A phase: Some queued nodes left (a)*) 4 i:=\\min\\{j\\geq 0: B[j]\\neq \\emptyset\\} (*Smallest nonempty bucket (b)*) 5 R:=\\emptyset (*No nodes deleted for bucket B[i] yet*) 6 while B[i]\\neq \\emptyset do (*New phase (c)*) 7 Req:=findRequests(B[i],light) (*Create requests for light edges (d)*) 8 R:=R\\cup B[i] (*Remember deleted nodes (e)*) 9 B[i]:=\\emptyset (*Current bucket empty*) 10 relaxRequests(Req) (*Do relaxations, nodes may (re)enter B[i] (f)*) 11 Req:=findRequests(R,heavy) (*Create requests for heavy edges (g)*) 12 relaxRequests(Req) (*Relaxations will not refill B[i] (h)*) 13 14 function findRequests(V',kind:\\{\\text{light}, \\text{heavy}\\}) :set of Request 15 return \\{(w, \\operatorname{tent}(v)+c(v,w)): v\\in V' \\land (v,w) \\in E_\\text{kind}\\} 16 17 procedure relaxRequests(Req) 18 foreach (w, x)\\in Req do relax(w,x) 19 20 procedure relax(w,x) (*Insert or move w in B if x *) 21 if x then 22 B[\\lfloor \\operatorname{tent}(w)/\\Delta\\rfloor]:=B[\\lfloor \\operatorname{tent}(w)/\\Delta\\rfloor]\\setminus \\{w\\} (*If in, remove from old bucket*) 23 B[\\lfloor x/\\Delta\\rfloor]:=B[\\lfloor x/\\Delta\\rfloor]\\cup \\{w\\} (*Insert into new bucket*) 24 \\operatorname{tent}(w):=x Let C_\\Delta denote the set of all node pairs \\langle u,v \\rangle connected by some \\Delta -path (u,\\dots, v) and let n_\\Delta:=|C_{\\Delta}| . Similarly, define C_{\\Delta+} as the set of triples \\langle u,v',v \\rangle such that \\langle u,v' \\rangle \\in C_\\Delta and (v',v) is a light edge and let m_\\Delta:=|C_{\\Delta+}| . The sequential delta-stepping algorithm needs at most \\mathcal{O} (n+m + n_\\Delta + m_\\Delta + L/\\Delta) operations. A simple parallelization runs in time \\mathcal{O} \\left(\\frac{L}{\\Delta}\\cdot d\\ell_\\Delta \\log n\\right) . If we take \\Delta = \\Theta(1/d) for graphs with maximum degree d and random edge weights uniformly distributed in [0,1] , the sequential version of the algorithm needs \\mathcal{O}(n+m+dL) total average-case time and a simple parallelization takes on average \\mathcal{O}(d^2 L \\log^2n) . Input: A graph G=(V,E,w) , vertex radii r(\\cdot) , and a source node s . Output: The graph distances \\delta(\\cdot) from s . 1 \\delta(\\cdot)\\leftarrow +\\infty , \\delta(s)\\leftarrow 0 2 foreach v \\in N(s) do \\delta(v)\\leftarrow w(s,v) , S_0\\leftarrow \\{s\\} , i \\leftarrow 1 3 while |S_{i-1}| do 4 d_i\\leftarrow \\min_{v\\in V\\setminus S_{i-1}}\\{\\delta(v) + r(v)\\} 5 repeat 6 foreach u \\in V\\setminus S_{i-1} s.t \\delta(u) \\leq d_i do 7 foreach v \\in N(u)\\setminus S_{i-1} do 8 \\delta(v) \\leftarrow \\min\\{\\delta(v), \\delta(u)+w(u,v)\\} 9 until no \\delta(v)\\leq d_i was updated 10 S_i=\\{v\\;|\\;\\delta(v)\\leq d_i\\} 11 i=i+1 12 return \\delta(\\cdot) For all S\\subseteq V , define N(S)=\\bigcup_{u\\in S}\\{v\\in V\\mid d(u,v)\\in E\\} to be the neighbor set of S. During the execution of standard breadth-first search or Dijkstra's algorithm, the frontier is the neighbor set of all visited vertices. In the Radius-Stepping algorithm, a new round distance d_i is decided on each round with the goal of bounding the number of substeps. The algorithm takes a radius r(v) for each vertex and selects a d_i on step i by taking the minimum \\delta(v) + r(v) over all v in the frontier (Line 4). Lines 5-9 then run the Bellman-Ford substeps until all vertices with radius less than d_i are settled. Vertices within d_i are then added to the visited set S_i . All neighbors of A are relaxed and S_0=\\{A\\} . The variable d_1 is chosen to be equal to 4 and the neighbors of the vertices B, E and G are relaxed. S_1=\\{A,B,E,G\\} The variable d_2 is chosen to be equal to 6 and no values are changed. S_2=\\{A,B,C,D,E,G\\} . The variable d_3 is chosen to be equal to 9 and no values are changed. S_3=\\{A,B,C,D,E,F, G\\} . The algorithm terminates.",
  "categories": [
    "23221441",
    "23603337",
    "26220375"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1315062833",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1759591859.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001315062833",
    "type": "webpage",
    "title": "Parallel single-source shortest path algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/parallel-single-source-shortest-path-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          13
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          13
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001315062833",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1315062833",
    "note": "Immutable snapshot enwiki-001315062833"
  }
}