owlingcode

Types of Shortest Path Problems

Different shortest path algorithms solve different variants of the problem:

Dijkstra's Algorithm

Finds shortest paths from a source vertex to all other vertices in graphs with non-negative weights:

const int INF = 1e9;

vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while(!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if(d > dist[u]) continue; // Skip outdated entries
        
        for(auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            
            if(dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

// Dijkstra with path reconstruction
pair<vector<int>, vector<int>> dijkstraWithPath(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INF);
    vector<int> parent(n, -1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while(!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if(d > dist[u]) continue;
        
        for(auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            
            if(dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
    
    return {dist, parent};
}

// Reconstruct path from start to target
vector<int> reconstructPath(int start, int target, vector<int>& parent) {
    vector<int> path;
    for(int v = target; v != -1; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    
    if(path.empty() || path[0] != start) {
        return {}; // No path exists
    }
    return path;
}
                    

Bellman-Ford Algorithm

Handles negative edge weights and detects negative cycles:

// Bellman-Ford algorithm
pair<vector<long long>, bool> bellmanFord(int start, int n, vector<tuple<int, int, int>>& edges) {
    vector<long long> dist(n, LLONG_MAX);
    dist[start] = 0;
    
    // Relax edges V-1 times
    for(int i = 0; i < n - 1; i++) {
        for(auto& edge : edges) {
            int u, v, weight;
            tie(u, v, weight) = edge;
            
            if(dist[u] != LLONG_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
    
    // Check for negative cycles
    bool hasNegativeCycle = false;
    for(auto& edge : edges) {
        int u, v, weight;
        tie(u, v, weight) = edge;
        
        if(dist[u] != LLONG_MAX && dist[u] + weight < dist[v]) {
            hasNegativeCycle = true;
            break;
        }
    }
    
    return {dist, hasNegativeCycle};
}

// SPFA (Shortest Path Faster Algorithm) - optimized Bellman-Ford
vector<long long> spfa(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<long long> dist(n, LLONG_MAX);
    vector<bool> inQueue(n, false);
    vector<int> count(n, 0); // Number of times each vertex is relaxed
    
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    inQueue[start] = true;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for(auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            
            if(dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                if(!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    count[v]++;
                    
                    // Negative cycle detection
                    if(count[v] >= n) {
                        return {}; // Negative cycle detected
                    }
                }
            }
        }
    }
    
    return dist;
}
                    

Floyd-Warshall Algorithm

Finds shortest paths between all pairs of vertices:

// Floyd-Warshall for all-pairs shortest paths
vector<vector<long long>> floydWarshall(vector<vector<long long>>& graph) {
    int n = graph.size();
    vector<vector<long long>> dist = graph;
    
    // Initialize diagonal to 0
    for(int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }
    
    // Floyd-Warshall main loop
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(dist[i][k] != LLONG_MAX && dist[k][j] != LLONG_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    return dist;
}

// Floyd-Warshall with path reconstruction
pair<vector<vector<long long>>, vector<vector<int>>> floydWarshallWithPath(vector<vector<long long>>& graph) {
    int n = graph.size();
    vector<vector<long long>> dist = graph;
    vector<vector<int>> next(n, vector<int>(n, -1));
    
    // Initialize next matrix
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(graph[i][j] != LLONG_MAX && i != j) {
                next[i][j] = j;
            }
        }
        dist[i][i] = 0;
    }
    
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(dist[i][k] != LLONG_MAX && dist[k][j] != LLONG_MAX &&
                   dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
            }
        }
    }
    
    return {dist, next};
}

// Reconstruct path using Floyd-Warshall next matrix
vector<int> reconstructFloydPath(int start, int end, vector<vector<int>>& next) {
    if(next[start][end] == -1) return {}; // No path
    
    vector<int> path = {start};
    while(start != end) {
        start = next[start][end];
        path.push_back(start);
    }
    return path;
}
                    

Advanced Shortest Path Problems

K Shortest Paths

Find the k shortest paths between two vertices:

// Yen's algorithm for K shortest paths
vector<vector<int>> kShortestPaths(int start, int end, int k, 
                                  vector<vector<pair<int, int>>>& adj) {
    vector<vector<int>> paths;
    priority_queue<pair<int, vector<int>>, 
                   vector<pair<int, vector<int>>>,
                   greater> candidates;
    
    // Find shortest path
    auto [dist, parent] = dijkstraWithPath(start, adj);
    if(dist[end] == INF) return paths; // No path exists
    
    vector<int> shortestPath = reconstructPath(start, end, parent);
    paths.push_back(shortestPath);
    
    for(int k_i = 1; k_i < k; k_i++) {
        vector<int> prevPath = paths.back();
        
        for(int i = 0; i < prevPath.size() - 1; i++) {
            // Remove edge and find alternative path
            vector<vector<pair<int, int>>> modifiedAdj = adj;
            
            // Remove edges used in previous paths
            for(auto& path : paths) {
                if(path.size() > i && equal(path.begin(), path.begin() + i + 1, 
                                          prevPath.begin())) {
                    int u = path[i], v = path[i + 1];
                    // Remove edge u -> v from modifiedAdj
                    removeEdge(modifiedAdj, u, v);
                }
            }
            
            auto [newDist, newParent] = dijkstraWithPath(prevPath[i], modifiedAdj);
            if(newDist[end] != INF) {
                vector<int> spurPath = reconstructPath(prevPath[i], end, newParent);
                vector<int> fullPath(prevPath.begin(), prevPath.begin() + i);
                fullPath.insert(fullPath.end(), spurPath.begin(), spurPath.end());
                
                int pathCost = calculatePathCost(fullPath, adj);
                candidates.push({pathCost, fullPath});
            }
        }
        
        if(candidates.empty()) break;
        
        paths.push_back(candidates.top().second);
        candidates.pop();
    }
    
    return paths;
}
                    

Shortest Path with Constraints

// Shortest path with exactly k edges
vector<int> shortestPathKEdges(int start, int end, int k, 
                               vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<vector<int>> dp(k + 1, vector<int>(n, INF));
    vector<vector<int>> parent(k + 1, vector<int>(n, -1));
    
    dp[0][start] = 0;
    
    for(int edges = 1; edges <= k; edges++) {
        for(int u = 0; u < n; u++) {
            if(dp[edges - 1][u] == INF) continue;
            
            for(auto& edge : adj[u]) {
                int v = edge.first;
                int weight = edge.second;
                
                if(dp[edges - 1][u] + weight < dp[edges][v]) {
                    dp[edges][v] = dp[edges - 1][u] + weight;
                    parent[edges][v] = u;
                }
            }
        }
    }
    
    // Reconstruct path
    vector<int> path;
    int curr = end, edgeCount = k;
    
    while(curr != -1 && edgeCount >= 0) {
        path.push_back(curr);
        curr = parent[edgeCount][curr];
        edgeCount--;
    }
    
    reverse(path.begin(), path.end());
    return path;
}