# Dijkstra's Algorithm — Efficient Shortest Paths (C++) ## Overview Dijkstra finds shortest paths from a source to all vertices when edge weights are non-negative. With a binary heap (priority queue) it runs in **O(E log V)**. ## Algorithm summary - Set `dist[source] = 0`, others `+∞`. - Use a min-priority queue keyed by current distance. - Repeatedly extract nearest vertex `u` and relax its outgoing edges: `dist[v] = min(dist[v], dist[u] + w)`. ## Complexity - Time: **O(E log V)** using a min-heap (priority queue) - Space: **O(V + E)** ## Reference & implementation notes The repo contains a simple implementation (index-based arrays, O(V^2) selection in `min1`): `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/Dijstra.cpp`. ### Snippet (selection + relax): ```cpp int min1(...) { // picks unvisited node with smallest dist // linear scan implementation used in repo } void dijkstra(...) { while (n--) { int u = min1(...); for (auto &e: adj[u]) { if (pth[e.first][0].first > pth[u][0].first + e.second) { pth[e.first][0] = { pth[u][0].first + e.second, u }; } } } } ``` ## Practical tips - For performance on large sparse graphs, replace the linear `min1` with a priority queue (std::priority_queue with pairs and a visited set). - Dijkstra does **not** handle negative edge weights; use Bellman–Ford or Johnson for graphs with negatives. ## Source `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/Dijstra.cpp`