Algorithms

Searching & Sorting  Linear search scans each element until a target is found (or list ends). It requires no precondition on data ordering, and runs in O(n) time in the worst and average case (linear in list size) () (best-case O(1) if the first element is the target). This brute-force approach is practical for small or unsorted collections. Binary search, by contrast, operates on sorted arrays and uses a divide-and-conquer strategy: it compares the target with the mid element to halve the search space each step. This yields O(log n) time in the worst and average case (Sorting) (with a constant O(1) space overhead). Binary search’s best-case is O(1) if the mid comparison hits the target. Its efficiency makes it ideal for lookups in large sorted datasets or any scenario where maintaining sorted order is feasible. However, binary search requires sorted data – if the data isn’t sorted, the array must first be sorted (typically O(n log n)) before binary search can be used, which may dominate cost in one-off searches.

Classical sorting algorithms: Insertion sort builds a sorted list by inserting elements one by one into the correct position. It runs in O(n²) worst-case (when input is reverse sorted, each new element shifts an entire sorted subarray) and O(n²) on average (Sorting) (Sorting). However, it attains O(n) best-case when the input is already sorted or nearly sorted (Sorting), as each new element finds its place immediately. Insertion sort’s in-place operation (O(1) extra space) and efficiency on small or nearly-sorted inputs make it useful for small subproblems or as a base-case in hybrid algorithms.

Merge sort follows a divide-and-conquer approach: it recursively splits the array in half, sorts each half, then merges the sorted halves. Its time complexity is O(n log n) in the best, average, and worst cases (Sorting), since splitting always proceeds to log₂ n depth and merging costs O(n) per level. Merge sort’s space complexity is O(n) due to the auxiliary arrays used for merging. Notably, merge sort is stable (preserves input order for equal elements) and thus suitable for situations where stability matters (e.g. sorting database records by multiple keys). It’s the algorithm of choice for linked lists and external sorting on disk, where random access is slow.

Quicksort is often the fastest in practice for in-memory sorting. It works by choosing a pivot, partitioning the array into elements less than pivot and greater than pivot, then recursively sorting the partitions (Sorting) (Sorting). Its average and typical complexity is O(n log n) (Sorting), but the worst-case is O(n²) (Sorting) (Sorting) if poor pivots (e.g. always the smallest or largest element) cause highly unbalanced partitions. In practice, picking a random pivot or using “median-of-three” mitigates this risk (Sorting). Quicksort is in-place (O(log n) auxiliary stack space for recursion) but not stable. It’s favored for general-purpose sorting of arrays due to its excellent cache locality and low constant factors – many libraries’ default sort (e.g. C++ std::sort) use a variant of quicksort.

Heap sort uses a binary heap to repeatedly extract the minimum (or maximum) element. Building a heap takes O(n) time and then each of n deletions takes O(log n), yielding O(n log n) in worst and average cases (Sorting). Its best-case is also O(n log n) in typical implementations (the heap operations cost log n regardless of input order). Heap sort is in-place (O(1) auxiliary space) and has the advantage of a solid O(n log n) worst-case guarantee, but it is typically not stable and often slightly slower in practice than well-implemented quicksort due to poorer cache performance. It shines when worst-case performance must be avoided (e.g. real-time systems) or when sorting in place with minimal extra memory.

Complexity comparison: The table below summarizes classical sorting algorithms (for n elements):

Algorithm	Best Case	Average Case	Worst Case	Space (aux)	Stable?
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No

Each has use-cases: e.g. insertion sort for small or nearly-sorted inputs, merge sort for linked lists or external sorting, quicksort for general in-memory sorts, and heap sort when requiring worst-case guarantees.

Modern hybrid algorithms leverage these strengths. Timsort, for instance, is a hybrid algorithm (used in Python and Java’s sorting) that merges runs of presorted data. It is stable and runs in O(n log n) worst-case, but optimally adapts to partially sorted input, running in O(n) best-case (Timsort – Wikipedia). As Tim Peters quipped about Timsort: “It has no bad cases (O(N log N) is worst case; N–1 compares is best)” (Timsort – Wikipedia). Introsort (introspective sort) is another pragmatic hybrid: it begins as quicksort and monitors recursion depth. If partitioning degrades (too many levels), it switches to heap sort to ensure O(n log n) worst-case (Introsort – Wikipedia). Introsort (used in C++ std::sort) combines quicksort’s typical speed with heap sort’s safety, making it fast on average and optimal in worst-case (Introsort – Wikipedia). These modern variants, along with others like samplesort and dual-pivot quicksort, illustrate how algorithm engineering blends theoretical guarantees with practical performance (Introsort – Wikipedia) (Timsort – Wikipedia).

Hashing  A hash function maps keys to integer hash codes (indices) such that keys are “randomly” distributed among table slots. Good hash functions aim for uniform distribution – each table slot equally likely for a random key () – and minimize collisions (distinct keys mapping to the same index). In practice, simple schemes like division (h(k) = k mod m) or multiplication work well with appropriate table size and constants (). Critical properties of hash functions are determinism (same key yields same code), speed, and collision resistance (they should avoid systematic collisions for expected inputs). Cryptographic hash functions add a stronger notion of collision resistance (hard to find any two distinct inputs with same hash), but for general hash tables, the goal is to spread keys uniformly to reduce collision frequency ().

A hash table stores key–value pairs in an array, using the hash of a key to index where the pair should reside. Ideally, a lookup, insertion, or deletion can then occur in O(1) time by direct index access (). However, collisions require special handling. Separate chaining places colliding items into a linked list (or bucket) at that slot (). Open addressing instead finds another slot within the table when a collision occurs (by probing a sequence of slots, e.g. linear or quadratic probing, or double hashing) (). In chaining, the table stores pointers to heads of lists; in open addressing, all data reside in the array itself.

Under assumptions of simple uniform hashing (each key equally likely to hash to any slot) (), one can analyze average-case performance. With n keys in m slots (load factor α = n/m), the expected search cost (for unsuccessful search or a random successful search) is O(1 + α) () (). For a fixed α treated as constant, this means average lookup time is Θ(1). For example, Cormen et al. note that in a chaining-based hash table, an unsuccessful search examines ~α elements on average (). Insertions are O(1) on average (compute hash + insert at a bucket head or find a free slot). Deletions in chaining are O(1) given pointer manipulations, whereas in open addressing deletion can be tricky (often handled by marking tombstones to avoid breaking probe chains) ().

The worst-case for a hash table is much worse: O(n) time if all keys collide into one slot (degrading to a linked list) or if a pathological sequence of probes occurs in open addressing. Therefore, hash tables are usually analyzed in an average-case or amortized sense. Amortization comes into play when hash tables dynamically resize. A common strategy is to double the table size when α exceeds a threshold (e.g. 0.75) and rehash all keys. A resizing operation costs O(n) but happens infrequently, so its cost spread over many inserts yields amortized O(1) insert time. Thus, in practice we expect hash table ops to be constant time on average, while worst-case search or insert (without resizing) is O(n). If truly guaranteed O(1) worst-case is needed, other structures (e.g. trees or specialized hashing) are used.

Recent advances have produced hashing schemes with guaranteed bounds. Perfect hashing constructs a hash function with no collisions for a static set of n keys (Perfect hash function – Wikipedia) (Perfect hash function – Wikipedia). This yields O(1) worst-case lookup time (Perfect hash function – Wikipedia) – essentially array indexing after hashing – at the cost of extra space or setup time. A simple perfect hashing approach by Fredman–Komlós–Szemerédi uses two-level hashing: an initial hash distributes keys into buckets, then a second-level hash with carefully chosen parameters places each bucket’s keys into a collision-free secondary table (Dynamic perfect hashing – Wikipedia) (Dynamic perfect hashing – Wikipedia). The resulting structure uses O(n) space overall and finds keys in one or two memory accesses. Dynamic perfect hashing extends this idea to support insertions and deletions: if a collision occurs in a second-level table, that sub-table is rebuilt (using a new hash) in expected O(1) time, and if the overall structure grows, a full rehash can be done occasionally (Dynamic perfect hashing – Wikipedia) (Dynamic perfect hashing – Wikipedia). The result (Dietzfelbinger et al., 1994) is a dictionary with worst-case O(1) lookup and amortized O(1) insert/delete (Dynamic perfect hashing – Wikipedia) (Dynamic perfect hashing – Wikipedia). Another modern scheme, cuckoo hashing, uses two (or more) hash functions and guarantees O(1) worst-case lookup by storing each key in one of two possible slots and “kicking out” any occupant on collision. Pagh and Rodler’s seminal work on cuckoo hashing showed it achieves worst-case constant retrieval time (Cuckoo hashing – Wikipedia) while keeping inserts amortized O(1) (with small probability of expensive rehashes). These techniques, along with others like Hopscotch and Robin Hood hashing, improve predictability: they ensure that even in adversarial or unlucky cases, performance won’t dramatically degrade from the typical constant-time behavior of hashing (Cuckoo hashing – Wikipedia).

Asymptotic Worst-Case Time & Space Complexity  When analyzing algorithms, we often focus on how their resource usage scales with input size n. Big-O notation gives an upper bound on growth: T(n) = O(f(n)) means that for large n, T(n) grows on the order of f(n) or slower (within a constant factor). Big-O notation is crucial for comparing algorithms in a machine-independent way. In particular, worst-case time complexity (often denoted Big-O) describes the maximum amount of time an algorithm could take on any input of size n. Worst-case analysis is important because it guarantees performance: “Worst-case analysis gives a safe analysis (the worst case is never underestimated), but one which can be overly pessimistic.” (Best, worst and average case – Wikipedia). By focusing on the upper bound, we ensure the algorithm will never exceed that time, an important consideration for real-time systems, security (no pathological inputs can cause delays), or simply to understand the algorithm’s guaranteed efficiency.

Algorithms are often classified by their Big-O time complexity classes. Common classes (from fastest-growing runtime to slowest) include: O(1) – constant time, e.g. array access by index is constant regardless of array length (); O(log n) – logarithmic, e.g. binary search on a sorted array runs in time proportional to log₂ n (Sorting); O(n) – linear, e.g. scanning an unsorted list of n items (linear search) is proportional to n (); O(n log n) – log-linear, typical of efficient sorts like mergesort (Sorting) or heapsort, combining a linear and logarithmic factor; O(n²) – quadratic, e.g. insertion sort’s worst case double-loop over n elements (Sorting) or computing all pairs of interactions among n items; O(n³) – cubic, e.g. the Floyd–Warshall algorithm for all-pairs shortest paths on n nodes runs in Θ(n³) time (Floyd–Warshall algorithm – Wikipedia); and exponential O(2^n) or *O(_n!)_ – which become infeasible except for very small n (for instance, exhaustive search on n elements, or the brute-force solution to the Traveling Salesman Problem which is O(n!)). An algorithm with complexity O(1) or O(log n) is considered excellent, scaling to large inputs, whereas one with O(2^n) or worse is usually impractical beyond small n.

It’s worth noting these classes describe asymptotic behavior – for large n – and ignore constant factors or lower-order terms. They let us reason about trade-offs: e.g. an O(n log n) algorithm (like sorting) will eventually outperform an O(n²) algorithm (like basic matrix multiplication) as n grows, despite the latter potentially being faster for small inputs due to smaller constants. In algorithm design, we strive for lower complexity classes, especially as n scales.

While worst-case Big-O is most commonly used, sometimes average-case or amortized analysis is more informative. Average-case complexity assumes a probability distribution over inputs and gives expected performance. For instance, quicksort’s average time is O(n log n) even though worst-case is O(n²) (Sorting), and in practice the average-case is what one typically observes with randomized pivots. Average-case analysis can be tricky – one must define “typical” inputs rigorously, which is not always possible (Best, worst and average case – Wikipedia). Amortized analysis considers the cost per operation over a sequence of operations. It is useful when occasional expensive operations occur but are offset by many cheap ones. A classic example is the dynamic array (or vector) expansion: appending n elements, where the array doubles in size when full, takes total O(n) time to reallocate copies over the whole sequence, so the amortized cost per append is O(1) even though an individual resize operation is O(n). In hashing, as discussed, rehashing incurs a large cost but happens rarely enough that the amortized insert time remains constant (Dynamic perfect hashing – Wikipedia). Amortized analysis gives a guarantee about the long-term average performance, which can be as useful as worst-case for operations in bulk or algorithms with phases of different costs.

In summary, Big-O worst-case analysis provides an assurance of an algorithm’s upper-bound time (and space) requirements, while average-case and amortized analyses offer refined insights when worst-case is too pessimistic. A well-rounded understanding considers all: e.g. hash tables have O(1) average time and O(n) worst-case, so one might pair them with worst-case-efficient structures (like trees) in critical applications, or use randomized hashing to make adverse inputs unlikely. Algorithm designers often target good worst-case complexity but will settle for excellent average performance with mitigations for the worst case.

Algorithm Design Techniques  Designing efficient algorithms often involves general paradigms that provide a recipe for solving problems:

• Greedy Algorithms: A greedy algorithm builds a solution iteratively, making the locally optimal choice at each step in hopes of reaching a global optimum. Greedy strategies require two key properties: the greedy-choice property (one can assemble an optimal solution by making optimal local choices) and optimal substructure (optimal solutions to the whole contain optimal solutions to subproblems) (). If these hold, a greedy algorithm can be both correct and very efficient. For example, in the activity selection problem (scheduling the maximum number of mutually compatible activities), a greedy approach selects the activity that finishes first, then recurses on the remaining time (ICS 311 #13: Greedy Algorithms ) (ICS 311 #13: Greedy Algorithms ). This works because one can prove the earliest finishing activity is part of some optimal solution and that the subproblem left after choosing it is again an optimal scheduling problem (ICS 311 #13: Greedy Algorithms ) (ICS 311 #13: Greedy Algorithms ). This greedy choice property, combined with optimal substructure, guarantees optimality. The resulting algorithm runs in O(n log n) after sorting activities by finish time, far faster than brute-force checking of all subsets. Other classic greedy algorithms include Kruskal’s MST algorithm (repeatedly add the smallest-weight edge that doesn’t create a cycle) and Prim’s MST (grow tree from a start node by adding the smallest edge out of the tree). Both rely on cut-optimality properties that justify greedy choices. Huffman coding (greedily merge lowest-frequency symbols) is another example – it constructs an optimal prefix code by repeatedly combining least frequent symbols (ICS 311 #13: Greedy Algorithms – University of Hawaii System). Greedy algorithms tend to be straightforward and fast (often O(n log n) due to sorting), but one must prove that greedy choices lead to an optimal solution (counterexamples exist when the properties don’t hold). If the greedy-choice property fails, a greedy method can get stuck with a suboptimal solution. But when it succeeds, greedy algorithms are very powerful due to their simplicity and efficiency.
• Dynamic Programming (DP): Dynamic programming applies when a problem has optimal substructure and overlapping subproblems. Optimal substructure means an optimal solution can be composed of optimal solutions to sub-instances of the problem () (Optimal substructure – Wikipedia). Overlapping subproblems means the recursive sub-instances are reused many times (Overlapping subproblems – Wikipedia). DP works by solving each subproblem once (often storing the results in a table) and reusing those results, rather than recomputing them. This yields drastic speedups over naive recursion when many calls repeat the same subproblem (e.g. computing Fibonacci numbers recursively has 2^n time but DP does it in n). A DP solution typically has two steps: formulate a recurrence relation (or state transition) that expresses the optimal solution in terms of smaller subproblems, and compute that recurrence efficiently (either top-down with memoization or bottom-up with tabulation). For example, the Floyd–Warshall algorithm for all-pairs shortest paths is a DP: it builds up solutions for increasing subsets of intermediate vertices. Its state definition dist[k][i][j] (shortest distance from i to j using only vertices 1…k as intermediates) has the recurrence dist[k][i][j] = min( dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j] ). This yields a triple nested loop implementation in Θ(n³) time (Floyd–Warshall algorithm – Wikipedia), significantly simpler than running n times Dijkstra (Θ(n · (V log V + E)) in dense graphs). Another example: the classic matrix-chain multiplication DP computes the optimal way to parenthesize matrix products. It defines dp[i][j] as the minimum cost to multiply matrices i through j, and finds a split k that minimizes dp[i][k] + dp[k+1][j] + cost of multiplying the two results. This DP is O(n³) for n matrices, versus exponential brute force. Dynamic programming often requires careful identification of subproblem structure and sometimes results in higher polynomial runtime, but it finds optimal solutions where greedy or other heuristics fail.

Modern DP techniques include methods to optimize naive DP recurrences. For instance, Knuth optimization (or the Knuth–Yao optimization) can reduce certain DP from O(n³) to O(n²) when the DP’s “optimal split index” for [i, j] is monotonic with respect to i and j (Knuth’s Optimization in Dynamic Programming – GeeksforGeeks). This applies to problems like optimal binary search tree or matrix-chain multiplication under specific conditions. Similarly, divide and conquer DP optimization (Aliens method) can optimize certain DP with quadratically costly transitions to O(n log n). These advanced techniques leverage structural properties of the DP solution to prune the state space or reduce transitions, making DP feasible for larger inputs. As an example, Knuth optimization is used in computing optimal binary search tree layouts, reducing the time from cubic to quadratic by exploiting the “optimal root” property (the index of the root in the optimal solution for a range is non-decreasing as the range moves) (Knuth’s Optimization in Dynamic Programming – GeeksforGeeks).

In summary, dynamic programming is the tool of choice for optimization problems that can be broken into overlapping sub-tasks. It guarantees an optimal solution and is often polynomial in complexity (as opposed to brute-force exponential), albeit sometimes heavy in time or space. Careful DP design and optimizations can further tame the complexity, as seen in countless applications from edit distance (string similarity) to knapSack, and from parsing algorithms to game theory.

• Divide-and-Conquer: This design paradigm breaks a problem into independent subproblems, solves each recursively, and then combines their solutions. Merge sort is a canonical example: divide the array into two halves, sort each (recursively), then merge – the combination step – in linear time () (). The recurrence T(n) = 2 T(n/2) + O(n) (for merging) yields T(n) = O(n log n) by the Master Theorem. Quicksort similarly divides (partitions) and then recurses, with a trivial combine step (Sorting) (Sorting). Binary search divides the search range in half each time. The efficiency of divide-and-conquer often comes from halving (or otherwise reducing) the problem size at each step, leading to logarithmic recursion depth. Master Theorem provides a convenient way to solve recurrences common in divide-and-conquer: for example, if an algorithm divides the input into a subproblems each of size 1/b of the original, and spends O(n^d) time outside the recursive calls, then the complexity is: Θ(n^d) if d > log_b a; Θ(n^d log n) if d = log_b a; or Θ(n^(log_b a))* if d < log_b a (Kruskal’s algorithm – Wikipedia). Classic applications: Strassen’s algorithm for matrix multiplication uses divide-and-conquer to achieve O(n^2.807) < n^3 by splitting matrices; the Fast Fourier Transform (FFT) divides a polynomial evaluation problem into two half-size subproblems achieving O(n log n); and many geometric algorithms recursively divide point sets or spatial dimensions. Divide-and-conquer can also parallelize naturally (different subproblems can run on different processors) and is cache-friendly due to working on smaller subproblems fits in cache. The downside can be recursion overhead and the need for combining results. Still, it’s a pervasive technique – whenever a problem can be cleanly split and merged, divide-and-conquer is likely to yield an efficient solution.

Graph Algorithms  Graphs (collections of vertices connected by edges) are a fundamental model, and many classic algorithms tackle graph traversal and optimization problems:

• Graph Traversals (BFS vs DFS): To traverse or explore all nodes reachable in a graph, we typically use Breadth-First Search (BFS) or Depth-First Search (DFS). BFS explores level by level: starting from a source node, it visits all neighbors (distance 1), then all nodes at distance 2, etc., using a queue to maintain the frontier. BFS runs in O(V + E) time – linear in the number of vertices and edges (Why is the complexity of both BFS and DFS O(V+E)? – GeeksforGeeks) – since each vertex is enqueued/dequeued once and each edge is considered at most twice (in an undirected graph) or once (directed). BFS also uses O(V) space for the queue and visited set. A key feature: BFS finds shortest paths in an unweighted graph. If edges are unweighted (or all weight = 1), the first time BFS reaches a node, it has found the minimum number of hops from the source ([PDF] Breadth First Search, Dijkstra’s Algorithm for Shortest Paths). Thus BFS is widely used for shortest-path problems in unweighted networks, as well as in peer-to-peer networking, garbage collection (Cheney’s algorithm), and broadcasting in network graphs.

DFS, in contrast, dives as deep as possible along one path before backtracking. It uses a stack (recursively or explicitly) to remember to return to prior vertices. It also runs in O(V + E) time for adjacency-list graphs (Why is the complexity of both BFS and DFS O(V+E)? – GeeksforGeeks), with O(V) space for recursion stack/visited set. DFS does not inherently find shortest paths (it may go on a long path before exploring shorter alternatives), but it has other applications. It can be used to classify edges and detect cycles (back edges indicate a cycle), to perform topological sorting (ordering vertices such that all directed edges go from earlier to later in the order), and to identify connected components. For example, Kosaraju’s algorithm for strongly connected components runs DFS twice (on the graph and its transpose). DFS is also a basis for backtracking algorithms (like solving puzzles, where you DFS the state space). In summary, BFS is typically chosen when shortest distance or layer-by-layer processing is needed, while DFS is chosen for depth-based exploration, cycle detection, topological sorts, and scenarios requiring recursion.

Both BFS and DFS are linear in graph size and thus very efficient. They differ in the order they explore nodes, which leads to different by-products (BFS yields shortest-path tree; DFS yields discovery/finish times that help find bridges, articulation points, etc.). In an n-node, m-edge graph, O(V + E) = O(n + m) – for dense graphs, this is ~O(n²), for sparse graphs it’s near-linear. This linearithmic growth is feasible for quite large graphs (millions of nodes/edges). In practice, graph libraries and algorithms rely on these traversals as subroutines for more complex tasks.

• Minimum Spanning Trees (MSTs): A spanning tree of a connected graph is a subset of edges forming a tree that connects all vertices. A minimum spanning tree is the spanning tree with minimum total edge weight (Minimum spanning tree – Wikipedia). MSTs are important for network design problems – e.g. laying out cables or pipelines cheaply, or constructing a minimum-wire topology connecting nodes. Two classical greedy algorithms find MSTs efficiently: Kruskal’s and Prim’s. Kruskal’s algorithm sorts all edges by weight and then iteratively adds the smallest edge that doesn’t form a cycle (using a Union-Find structure for cycle detection). This produces an MST in O(E log E) time from sorting (which dominates the union-find operations that are almost O(1) amortized) (Kruskal’s algorithm – Wikipedia). Since E log E is O(E log V) in the worst case (there are at most V(V−1)/2 edges), Kruskal’s complexity is often written O(E log V) (Kruskal’s algorithm – Wikipedia). It’s very effective for sparse graphs (where E is on the order of V). Kruskal’s is also easy to implement and understand. Its drawback is needing to sort edges upfront and to potentially handle a large number of edges for dense graphs. Prim’s algorithm constructs the MST by growing one tree. It starts from an arbitrary root and at each step adds the smallest-weight edge that connects a vertex in the tree to a vertex outside the tree. Using a min-priority queue (min-heap) for selecting the next edge, Prim’s runs in O(E log V) time (Prim’s Algorithm). In dense graphs where E ~ V², Prim’s can be optimized by using a simple array to pick the minimum edge in O(V²) time, which may be faster than a heap for large V (since O(V²) vs O(V² log V) with a heap) (Time and Space Complexity Analysis of Prim’s Algorithm). Generally, Prim’s is often preferred for dense graphs or when a good adjacency structure is available, while Kruskal’s can be faster for sparse graphs or when edges are already sorted (or can be streamed sorted). Both algorithms exploit a greedy choice: at each step add the smallest edge that preserves feasibility, which is justified by the cut and cycle properties of MSTs (proofs given in texts like CLRS). Use cases: In practice, MST algorithms are used in network design (minimum-cost spanning networks), clustering analysis (single-link clustering uses MST concepts), and creating mazes (an MST of a grid yields a maze). If the graph is very large (e.g. millions of edges), using a specialized variant like Kruskal with union-find or Prim’s with a Fibonacci heap (improving Prim’s to O(E + V log V)) is critical. Many libraries implement a version of Prim’s or Kruskal’s; e.g. Jarnik–Prim is often easier when you have an adjacency list, while Kruskal can leverage global edge ordering. (image) A weighted graph (above) and its minimum spanning tree (below). The MST connects all vertices with total minimal weight (Minimum spanning tree – Wikipedia).
• Shortest Paths: In weighted graphs (where each edge has a length or cost), the task of finding shortest paths is fundamental. Different algorithms apply depending on weight conditions: Dijkstra’s algorithm finds the shortest path distances from a single source to all other vertices, provided edge weights are non-negative. It operates similarly to BFS but uses a priority queue to always “greedily” pick the next closest vertex to finalize. Initially, distance to source = 0 and others = ∞; then repeatedly extract the vertex u with smallest tentative distance and relax its outgoing edges (update neighbor distances) (Dijkstra’s algorithm – Wikipedia). Using a binary heap, Dijkstra’s runs in O((V + E) log V) time (Dijkstra’s algorithm – Wikipedia), which is O(E log V) in the worst case since E ≥ V–1. (With a Fibonacci heap, it improves to O(V log V + E) (Dijkstra’s algorithm – Wikipedia), but in practice binary heaps are usually faster due to smaller constants). Dijkstra’s is very efficient for reasonably sparse graphs and is widely used in routing (e.g. GPS navigation). It will not work correctly if there are negative-weight edges, as it can prematurely finalize a distance that later gets reduced via a negative edge. Bellman–Ford algorithm handles negative weights gracefully (still assuming no negative-weight cycles reachable from the source). It relaxes all edges V–1 times in a row, guaranteeing shortest distances propagate throughout the graph. This is O(V · E) time (Bellman–Ford algorithm – Wikipedia), which for dense graphs is O(V³) and for sparse is O(V · V) = O(V²). While slower, Bellman–Ford has the advantage of simplicity and the ability to detect negative cycles: after V–1 passes, one more pass is run – if any distance improves, there is a negative cycle ([data structures] Time complexity of the Bellman Ford algorithm on …). Its typical use cases are scenarios with modest graph sizes or where negative weights are present (e.g. certain economic models or arbitrage detection). If E is extremely large (E ~ V²), even Bellman–Ford becomes costly; in such cases, one might use Johnson’s algorithm for all-pairs (which uses Bellman–Ford once and then Dijkstra V times) or other specialized methods. Floyd–Warshall algorithm computes shortest paths between all pairs of vertices. It’s a DP-based algorithm that incrementally allows each vertex as an intermediate stop between others. Floyd–Warshall runs in Θ(V³) time (Floyd–Warshall algorithm – Wikipedia) and Θ(V²) space, by updating a distance matrix in triple nested loops. Though cubic, it is often competitive for graphs up to a few hundred vertices. It can handle negative weights (as long as no negative cycles exist – if there is one, it can detect it by seeing a distance becoming smaller than zero on the V_th iteration). The simplicity of Floyd–Warshall (just a few lines of nested loops) makes it a clear choice for dense graphs or when _V is not too large. For example, in routing between all pairs of nodes in a network with up to, say, 400 nodes, Floyd–Warshall is feasible (400³ = 64 million operations). For larger graphs, one would use repeated single-source computations (e.g. run Dijkstra from each vertex, which is O(V E log V) – potentially better for sparse graphs) or other all-pairs methods. Choosing the right algorithm: If all edge weights are equal (or unweighted graph), BFS from the source is actually the fastest way to get single-source shortest paths (O(V+E)). If weights are non-negative, Dijkstra’s is typically the best single-source choice (efficient and straightforward). If negative weights are present (but no negative cycles), Bellman–Ford or Johnson’s algorithm are used. For all-pairs shortest paths, if V is small or graph is dense, Floyd–Warshall is convenient; if V is larger and graph sparse, running Dijkstra from each node or Johnson’s (which uses V–1 Bellman–Ford + V Dijkstra’s) might be better. It’s notable that no general algorithm is known that’s significantly faster than O(V · E) for arbitrary weights – this is a subject of ongoing research (with recent progress for special cases or approximate distances).

In summary, graph algorithms like traversals (BFS/DFS), MST, and shortest paths are cornerstone techniques. They all illustrate key algorithmic ideas: BFS/DFS show linear-time graph exploration, MST algorithms show greedy strategy correctness, and shortest path algorithms show the power of greedy methods with proper data structures (Dijkstra) or DP (Bellman-Ford, Floyd-Warshall) in graph optimization. These algorithms, first formalized in texts like Introduction to Algorithms by Cormen et al., remain highly relevant – forming the backbone of routing protocols, network design, and countless applications in computer science and engineering (Kruskal’s algorithm – Wikipedia) (Dijkstra’s algorithm – Wikipedia).

References: Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd Ed. (MIT Press, 2009); Skiena, The Algorithm Design Manual (Springer, 2008); Kleinberg and Tardos, Algorithm Design (Addison-Wesley, 2005); and various algorithm references () (Sorting) (Kruskal’s algorithm – Wikipedia) (Dijkstra’s algorithm – Wikipedia). These provide formal proofs, additional variations, and in-depth discussion of the algorithms mentioned. The above content also incorporates insights from recent research (e.g. hashing advancements (Dynamic perfect hashing – Wikipedia) (Cuckoo hashing – Wikipedia)) and industry practices (like Timsort (Timsort – Wikipedia) and introsort (Introsort – Wikipedia)), bridging classic theory with modern application.