Dijkstra Algortihm: O(n²) Approach

Dijkstra's algorithm solves the single-source shortest path problem for graphs with non-negative edge weights. It efficiently computes the minimum distance from a starting vertex to all other vertices using a greedy approach.

Algorithm Overview

1. Initialization: Set the source distance to 0 and all other vertices to infinity.
2. Selection: Choose the unvisited vertex with the smallest current distance.
3. Relaxation: Update distances of adjacent vertices if a shorter path is found.
4. Marking: Mark the selected vertex as processed.
5. Iteration: Repeat until all vertices are processed.

Implementation Details

The O(n²) version uses an adjacency matrix and is suitable for dense graphs with fewer vertices (n ≤ 500).

Key Components:

• Adjacency Matrix: Stores edge weights, initialized to INF (∞).
• Distance Array: Tracks shortest distances from source.
• Visited Array: Marks vertices with confirmed shortest paths.

Optimized Implemantation

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

const int MAX_VERTICES = 505;
const int INFINITY = 1e9;

class DijkstraBasic {
private:
    int vertexCount;
    int edgeCount;
    int graph[MAX_VERTICES][MAX_VERTICES];
    int distances[MAX_VERTICES];
    bool processed[MAX_VERTICES];
    
public:
    DijkstraBasic(int v, int e) : vertexCount(v), edgeCount(e) {
        for (int i = 1; i <= vertexCount; i++) {
            for (int j = 1; j <= vertexCount; j++) {
                graph[i][j] = (i == j) ? 0 : INFINITY;
            }
        }
    }
    
    void addEdge(int from, int to, int weight) {
        graph[from][to] = min(graph[from][to], weight);
    }
    
    int findShortestPath(int source, int destination) {
        fill(distances, distances + MAX_VERTICES, INFINITY);
        fill(processed, processed + MAX_VERTICES, false);
        
        distances[source] = 0;
        
        for (int iteration = 1; iteration <= vertexCount; iteration++) {
            int current = -1;
            
            for (int vertex = 1; vertex <= vertexCount; vertex++) {
                if (!processed[vertex] && (current == -1 || distances[vertex] < distances[current])) {
                    current = vertex;
                }
            }
            
            if (current == -1) break;
            processed[current] = true;
            
            for (int neighbor = 1; neighbor <= vertexCount; neighbor++) {
                if (graph[current][neighbor] < INFINITY) {
                    int newDistance = distances[current] + graph[current][neighbor];
                    distances[neighbor] = min(distances[neighbor], newDistance);
                }
            }
        }
        
        return (distances[destination] == INFINITY) ? -1 : distances[destination];
    }
};

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    
    DijkstraBasic solver(vertices, edges);
    
    for (int i = 0; i < edges; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        solver.addEdge(u, v, w);
    }
    
    int result = solver.findShortestPath(1, vertices);
    cout << result << endl;
    
    return 0;
}

Dijkstra Algorithm: Priority Queue Optimization

For sparse graphs with many vertices, the priority queue implementation achieves O(m log n) complexity, where m is the number of edges.

Optimized Implementation with Min-Heap

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int MAX_VERTICES = 150005;
const int INFINITY = 1e9;

struct Edge {
    int to;
    int weight;
    int next;
};

class DijkstraOptimized {
private:
    int vertexCount;
    Edge edges[MAX_VERTICES];
    int adjacencyList[MAX_VERTICES];
    int edgeIndex;
    int distances[MAX_VERTICES];
    bool visited[MAX_VERTICES];
    
public:
    DijkstraOptimized(int v) : vertexCount(v), edgeIndex(0) {
        fill(adjacencyList, adjacencyList + MAX_VERTICES, -1);
    }
    
    void insertEdge(int from, int to, int weight) {
        edges[edgeIndex] = {to, weight, adjacencyList[from]};
        adjacencyList[from] = edgeIndex++;
    }
    
    int computeShortestPath(int source, int destination) {
        fill(distances, distances + MAX_VERTICES, INFINITY);
        fill(visited, visited + MAX_VERTICES, false);
        
        distances[source] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({0, source});
        
        while (!pq.empty()) {
            auto current = pq.top();
            pq.pop();
            
            int currentDistance = current.first;
            int currentVertex = current.second;
            
            if (visited[currentVertex]) continue;
            visited[currentVertex] = true;
            
            for (int i = adjacencyList[currentVertex]; i != -1; i = edges[i].next) {
                int neighborVertex = edges[i].to;
                int edgeWeight = edges[i].weight;
                
                if (distances[neighborVertex] > currentDistance + edgeWeight) {
                    distances[neighborVertex] = currentDistance + edgeWeight;
                    pq.push({distances[neighborVertex], neighborVertex});
                }
            }
        }
        
        return (distances[destination] == INFINITY) ? -1 : distances[destination];
    }
};

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    
    DijkstraOptimized solver(vertices);
    
    for (int i = 0; i < edges; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        solver.insertEdge(u, v, w);
    }
    
    int result = solver.computeShortestPath(1, vertices);
    cout << result << endl;
    
    return 0;
}

Important Considerations

• Negative Edges: Dijkstra cannnot handle negative weights as they violate the greedy selection principle.
• Unreachable Nodes: Check for INFINITY to determine if a vertex is unreachable.
• Memory Efficiency: Use adjacency lists for sparse graphs and adjacency matrices for dense graphs.