On Thu, Aug 27, 2026 at 12:26 AM Léo Hardt <[email protected]> wrote: > > Good evening, > > This patch lowers the complexity of a pathfinding algorithm > from O( V^2 + E ) to O( V + E ), by changing from a Dijkstra's > Algorithm to a Breadth-First Search traversal. > > The traversal algorithm used in 'shortest-paths.h' was an > implementation of Dijkstra's with a O(n) lookup min-heap, and > therefore O(n^2) total runtime. There was a FIXME note to > improve the algorithm since 757bf1dff. > > One possible solution would have been to use the fibonacci heap > found in GCC and still implement O( E + V log V) Dijkstra's. > But since all the edge weights are equal, we can switch to a > simpler and more efficient BFS and improve legibility. > > Fixed other TODO's in the file and updated the comments. > > Successfully bootstrapped GCC with the changes below. > Hopefully the digraph selftests are enough to validate this patch.
You want to CC David Malcolm (done) who contributed this and the sole user (the analyzer). Richard. > gcc/ChangeLog: > > * shortest-paths.h (enum shortest_path_sense): Update comment. > (shortest_paths): Change implemetation from Dijkstra's to BFS. > > Signed-off-by: Léo Hardt <[email protected]> > --- > gcc/shortest-paths.h | 105 +++++++++++++++---------------------------- > 1 file changed, 36 insertions(+), 69 deletions(-) > > diff --git a/gcc/shortest-paths.h b/gcc/shortest-paths.h > index 5351b7e3737..1267f487338 100644 > --- a/gcc/shortest-paths.h > +++ b/gcc/shortest-paths.h > @@ -1,4 +1,4 @@ > -/* Template class for Dijkstra's algorithm on directed graphs. > +/* Template class for BFS algorithm on directed graphs. > Copyright (C) 2019-2026 Free Software Foundation, Inc. > Contributed by David Malcolm <[email protected]>. > > @@ -41,7 +41,7 @@ enum shortest_path_sense > SPS_TO_GIVEN_TARGET: > from each node in a graph to the given target node. > > - The constructor runs Dijkstra's algorithm, and the results are > + The constructor runs BFS traversal, and the results are > stored in this class. */ > > template <typename GraphTraits, typename Path_t> > @@ -78,9 +78,9 @@ private: > > /* shortest_paths's constructor. > > - Use Dijkstra's algorithm relative to GIVEN_NODE to populate m_dist and > - m_best_edge with enough information to be able to generate Path_t > instances > - to give the shortest path... > + Use Breadth-First Search relative to GIVEN_NODE to populate M_DIST and > + M_BEST_EDGE with enough information to be able to generate Path_t > instances > + to give a minimal path... > SPS_FROM_GIVEN_ORIGIN: to each node in a graph from the origin node, or > SPS_TO_GIVEN_TARGET: from each node in a graph to the target node. */ > > @@ -96,78 +96,45 @@ shortest_paths (const graph_t &graph, > m_best_edge (graph.m_nodes.length ()) > { > auto_timevar tv (TV_ANALYZER_SHORTEST_PATHS); > + unsigned n_nodes = graph.m_nodes.length (); > + bool forward = sense == SPS_FROM_GIVEN_ORIGIN; > + auto_vec<unsigned> queue(n_nodes); > > - auto_vec<int> queue (graph.m_nodes.length ()); > - > - for (unsigned i = 0; i < graph.m_nodes.length (); i++) > + for (unsigned i = 0; i < n_nodes; i++) > { > m_dist.quick_push (INT_MAX); > m_best_edge.quick_push (NULL); > - queue.quick_push (i); > } > + > + queue.quick_push (given_node->m_index); > m_dist[given_node->m_index] = 0; > > - while (queue.length () > 0) > - { > - /* Get minimal distance in queue. > - FIXME: this is O(N^2); replace with a priority queue. */ > - int idx_with_min_dist = -1; > - int idx_in_queue_with_min_dist = -1; > - int min_dist = INT_MAX; > - for (unsigned i = 0; i < queue.length (); i++) > - { > - int idx = queue[i]; > - if (m_dist[queue[i]] < min_dist) > - { > - min_dist = m_dist[idx]; > - idx_with_min_dist = idx; > - idx_in_queue_with_min_dist = i; > - } > - } > - if (idx_with_min_dist == -1) > - break; > - gcc_assert (idx_in_queue_with_min_dist != -1); > - > - // FIXME: this is confusing: there are two indices here > - > - queue.unordered_remove (idx_in_queue_with_min_dist); > - > - node_t *n > - = static_cast <node_t *> (m_graph.m_nodes[idx_with_min_dist]); > + /* BFS traversal for minimal dist and source edge. > > - if (m_sense == SPS_FROM_GIVEN_ORIGIN) > - { > - int i; > - edge_t *succ; > - FOR_EACH_VEC_ELT (n->m_succs, i, succ) > - { > - // TODO: only for dest still in queue > - node_t *dest = succ->m_dest; > - int alt = m_dist[n->m_index] + 1; > - if (alt < m_dist[dest->m_index]) > - { > - m_dist[dest->m_index] = alt; > - m_best_edge[dest->m_index] = succ; > - } > - } > - } > - else > - { > - int i; > - edge_t *pred; > - FOR_EACH_VEC_ELT (n->m_preds, i, pred) > - { > - // TODO: only for dest still in queue > - node_t *src = pred->m_src; > - int alt = m_dist[n->m_index] + 1; > - if (alt < m_dist[src->m_index]) > - { > - m_dist[src->m_index] = alt; > - m_best_edge[src->m_index] = pred; > - } > - } > - } > - } > + Once we see a node, all nodes of lesser dist were visted. > + Hence we never requeue nodes and queue.length () <= N_NODES. > + For unconnected graphs, queue.length () < N_NODES. */ > + for (unsigned i_queue = 0; i_queue < queue.length (); ++i_queue) > + { > + unsigned curr_idx = queue[i_queue]; > + node_t *n = graph.m_nodes[curr_idx]; > + > + vec<edge_t*>& edges = forward ? n->m_succs : n->m_preds; > + > + int i_edge; > + edge_t *edge; > + FOR_EACH_VEC_ELT (edges, i_edge, edge) > + { > + node_t *next = forward ? edge->m_dest : edge->m_src; > + unsigned next_idx = next->m_index; > + if (m_dist[next_idx] == INT_MAX) > + { > + m_dist[next_idx] = 1 + m_dist[curr_idx]; > + m_best_edge[next_idx] = edge; > + queue.quick_push (next_idx); > + } > + } > + } > } > > /* Generate an Path_t instance giving the shortest path between OTHER_NODE > -- > 2.47.3 >
