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.
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
