Shortest Path Algorithms

When solving shortest path problems, different approaches are needed depending on the specific constraints and requirements. This article examines three distinct shortest path scenarios with their corresponding solutions.

Problem C: Shortest Path with Exponential Edge Weights

Problem Analysis

This problem presents a significant numerical challenge that standard shortest path algorithms cannot directly handle. The edge weights follow the pattern 2^K where K ranges from 0 to 500. Since these values exceed standard integer limits, modular arithmetic is required. However, a critical insight emerges when edges are processed in input order.

The key observation is that for any two connected vertices appearing earlier in the input sequence, the cumulative sum of all preceding edge weights (2^0 + 2^1 + ... + 2^(k-1) = 2^k - 1) is always less than 2^k. This means that if two vertices are already connected through earlier edges, that existing path is guaranteed to be shorter than any new edge connecting them.

This property allows us to solve the problem using a Union-Find data structure rather than traditional graph algorithms like Dijkstra. The approach processes edges sequentially, maintaining connectivity information and updating shortest distances only when encountering edges that connect previously disconnected components.

Implementation with Union-Find

#include <cstdio>
#include <cstring>
#define MOD 100000
#define MAXSIZE 105

int parent[MAXSIZE];
int distMatrix[MAXSIZE][MAXSIZE];
int vertexCount;

int findRoot(int x) {
    if (x == parent[x]) return x;
    parent[x] = findRoot(parent[x]);
    return parent[x];
}

int powerMod(int base, int exp) {
    if (exp == 0) return 1;
    if (exp % 2 == 1) return (base * powerMod(base, exp - 1)) % MOD;
    int halfResult = powerMod(base, exp / 2);
    return (halfResult * halfResult) % MOD;
}

void uniteComponents(int edgeIndex) {
    int u, v, edgeWeight;
    scanf("%d%d", &u, &v);
    
    edgeWeight = powerMod(2, edgeIndex);
    int rootU = findRoot(u);
    int rootV = findRoot(v);
    
    if (rootU != rootV) {
        // Update shortest distances between the two components
        for (int i = 0; i < vertexCount; i++) {
            int rootI = findRoot(i);
            if (rootI == rootU) {
                for (int j = 0; j < vertexCount; j++) {
                    int rootJ = findRoot(j);
                    if (rootJ == rootV) {
                        distMatrix[i][j] = distMatrix[j][i] = 
                            (distMatrix[i][u] + edgeWeight + distMatrix[v][j]) % MOD;
                    }
                }
            }
        }
        parent[rootV] = rootU;
    }
}

int main() {
    int edgeCount;
    while (scanf("%d%d", &vertexCount, &edgeCount) != EOF) {
        memset(distMatrix, -1, sizeof(distMatrix));
        for (int i = 0; i < vertexCount; i++) {
            parent[i] = i;
            distMatrix[i][i] = 0;
        }
        
        for (int i = 0; i < edgeCount; i++) {
            uniteComponents(i);
        }
        
        for (int i = 1; i < vertexCount; i++) {
            printf("%d\n", distMatrix[0][i]);
        }
    }
    return 0;
}

This solution effectively computes all-pairs shortest paths by leveraging the mathematical property of exponential weights and using union-find for efficient component management.

Problem D: Shortest Path with Lexicographically Minimum Route

Problem Analysis

This problem requires not only finding the shortest distance between two vertices but also outputting the lexicographically smallest path. The algorithm combines Dijkstra's shortest path algorithm with depth-first search to enumerate and compare potential paths.

A common pitfall in this problem involves the handling of paralel edges. When multiple edges exist between the same pair of vertices, an adjacency list representation prevents incorrect distance calculasions that can occur with adjacency matrices.

Common Implementation Mistakes

When iterating through adjacency lists, it's crucial to access vertex indices correctly. The adjacency list stores actual vertex numbers, not position indices:

// Correct traversal pattern
for (int j = 0; j < Adj[u].size(); j++) {
    int v = Adj[u][j].v;  // Extract actual vertex number
    if (!vis[v]) {
        if (d[u] + Adj[u][j].dis < d[v]) {
            d[v] = d[u] + Adj[u][j].dis;
            predecessor[v].clear();
            predecessor[v].push_back(u);
        } else if (d[u] + Adj[u][j].dis == d[v]) {
            predecessor[v].push_back(u);
        }
    }
}

Complete Solution Using Adjacency List

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define INFINITY 0x3fffffff
#define MAXVERTEX 10005

struct Edge {
    int target;
    int weight;
    Edge(int t, int w) : target(t), weight(w) {}
};

std::vector<Edge> graph[MAXVERTEX];
bool visited[MAXVERTEX];
int distance[MAXVERTEX];
std::vector<int> predecessor[MAXVERTEX];
std::vector<int> tempRoute;
std::vector<int> optimalRoute;

void computeShortestPath(int source) {
    std::fill(distance, distance + MAXVERTEX, INFINITY);
    distance[source] = 0;
    
    for (int i = 1; i <= MAXVERTEX - 1; i++) {
        int current = -1;
        int minDist = INFINITY;
        
        for (int j = 1; j < MAXVERTEX; j++) {
            if (!visited[j] && distance[j] < minDist) {
                current = j;
                minDist = distance[j];
            }
        }
        
        if (current == -1) return;
        visited[current] = true;
        
        for (size_t k = 0; k < graph[current].size(); k++) {
            int neighbor = graph[current][k].target;
            if (!visited[neighbor]) {
                int newDist = distance[current] + graph[current][k].weight;
                if (newDist < distance[neighbor]) {
                    distance[neighbor] = newDist;
                    predecessor[neighbor].clear();
                    predecessor[neighbor].push_back(current);
                } else if (newDist == distance[neighbor]) {
                    predecessor[neighbor].push_back(current);
                }
            }
        }
    }
}

void findOptimalPath(int source, int current) {
    if (source == current) {
        tempRoute.push_back(source);
        if (tempRoute > optimalRoute || optimalRoute.empty()) {
            optimalRoute = tempRoute;
        }
        tempRoute.pop_back();
        return;
    }
    
    tempRoute.push_back(current);
    for (size_t i = 0; i < predecessor[current].size(); i++) {
        findOptimalPath(source, predecessor[current][i]);
    }
    tempRoute.pop_back();
}

int main() {
    int vertexNum, edgeNum, startPoint, endPoint;
    while (scanf("%d%d%d%d", &vertexNum, &edgeNum, &startPoint, &endPoint) != EOF) {
        memset(visited, 0, sizeof(visited));
        for (int i = 1; i <= vertexNum; i++) {
            graph[i].clear();
            predecessor[i].clear();
        }
        tempRoute.clear();
        optimalRoute.clear();
        
        for (int i = 0; i < edgeNum; i++) {
            int a, b, w;
            scanf("%d%d%d", &a, &b, &w);
            graph[a].push_back(Edge(b, w));
            graph[b].push_back(Edge(a, w));
        }
        
        computeShortestPath(startPoint);
        
        if (distance[endPoint] == INFINITY) {
            printf("can't arrive\n");
        } else {
            printf("%d\n", distance[endPoint]);
            findOptimalPath(startPoint, endPoint);
            for (int i = optimalRoute.size() - 1; i >= 0; i--) {
                printf("%d ", optimalRoute[i]);
            }
            printf("\n");
        }
    }
    return 0;
}

The path comparison uses vector lexicographic ordering. Since both the temporary and optimal paths are stored in reverse order during traversal, comparing tempRoute > optimalRoute correctly identifies the lexicographically smallest path.

Problem E: Shortest Path with Dual Optimization Criteria

Problem Analysis

This problem extends the standard shortest path problem by introducing an additional cost metric. The goal is to find paths that minimize distance first, with cost as a tiebreaker when multiple paths share the same minimum distance.

Two solution approaches prove effective: Dijkstra's algorithm extended to handle dual criteria, and a depth-first search with pruning.

Dijkstra-Based Solution

#include <cstdio>
#include <vector>
#include <algorithm>
#define LIM 1005
#define MAXDIST 0x3fffffff

int adjacency[LIM][LIM];
int edgeCost[LIM][LIM];
bool marked[LIM];
int shortestDist[LIM];
int minCost[LIM];
int totalVertices;

void dijkstraWithCost(int source) {
    std::fill(shortestDist, shortestDist + LIM, MAXDIST);
    std::fill(minCost, minCost + LIM, MAXDIST);
    shortestDist[source] = 0;
    minCost[source] = 0;
    
    for (int i = 1; i <= totalVertices; i++) {
        int selected = -1;
        int currentMin = MAXDIST;
        
        for (int j = 1; j <= totalVertices; j++) {
            if (!marked[j] && shortestDist[j] < currentMin) {
                selected = j;
                currentMin = shortestDist[j];
            }
        }
        
        if (selected == -1) return;
        marked[selected] = true;
        
        for (int j = 1; j <= totalVertices; j++) {
            if (!marked[j] && adjacency[selected][j] != MAXDIST) {
                int viaSelected = shortestDist[selected] + adjacency[selected][j];
                int costViaSelected = minCost[selected] + edgeCost[selected][j];
                
                if (viaSelected < shortestDist[j]) {
                    shortestDist[j] = viaSelected;
                    minCost[j] = costViaSelected;
                } else if (viaSelected == shortestDist[j] && 
                           costViaSelected < minCost[j]) {
                    minCost[j] = costViaSelected;
                }
            }
        }
    }
}

int main() {
    int edgeNum, u, v, d, c, src, dst;
    while (scanf("%d%d", &totalVertices, &edgeNum) && totalVertices && edgeNum) {
        std::fill(adjacency[0], adjacency[0] + LIM * LIM, MAXDIST);
        std::fill(edgeCost[0], edgeCost[0] + LIM * LIM, MAXDIST);
        std::fill(marked, marked + LIM, false);
        
        for (int i = 0; i < edgeNum; i++) {
            scanf("%d%d%d%d", &u, &v, &d, &c);
            adjacency[u][v] = adjacency[v][u] = d;
            edgeCost[u][v] = edgeCost[v][u] = c;
        }
        
        scanf("%d%d", &src, &dst);
        dijkstraWithCost(src);
        printf("%d %d\n", shortestDist[dst], minCost[dst]);
    }
    return 0;
}

DFS-Based Solution with Pruning

#include <cstdio>
#include <algorithm>
#define LIM 1005
#define MAXVAL 0x3fffffff

int graph[LIM][LIM];
int costMatrix[LIM][LIM];
int visited[LIM];
int vertexCount;
int source, target;
int bestDistance, bestExpense;

void depthSearch(int current, int accumDist, int accumCost) {
    if (accumDist > bestDistance || 
        (accumDist == bestDistance && accumCost >= bestExpense)) {
        return;
    }
    
    if (current == target) {
        bestDistance = accumDist;
        bestExpense = accumCost;
        return;
    }
    
    for (int i = 1; i <= vertexCount; i++) {
        if (!visited[i] && graph[current][i] != MAXVAL) {
            visited[i] = true;
            depthSearch(i, accumDist + graph[current][i], 
                       accumCost + costMatrix[current][i]);
            visited[i] = false;
        }
    }
}

int main() {
    int edgeCount, a, b, distance, cost;
    while (scanf("%d%d", &vertexCount, &edgeCount) && vertexCount && edgeCount) {
        std::fill(graph[0], graph[0] + LIM * LIM, MAXVAL);
        std::fill(costMatrix[0], costMatrix[0] + LIM * LIM, MAXVAL);
        std::fill(visited, visited + LIM, false);
        bestDistance = MAXVAL;
        bestExpense = MAXVAL;
        
        for (int i = 0; i < edgeCount; i++) {
            scanf("%d%d%d%d", &a, &b, &distance, &cost);
            graph[a][b] = graph[b][a] = distance;
            costMatrix[a][b] = costMatrix[b][a] = cost;
        }
        
        scanf("%d%d", &source, &target);
        visited[source] = true;
        depthSearch(source, 0, 0);
        printf("%d %d\n", bestDistance, bestExpense);
    }
    return 0;
}

The DFS approach includes pruning conditions that skip exploration when the accumulated distance already exceeds the best found solution, or when distances match but costs are higher. This significantly improves performance for dense graphs.

Key Takeaways

Each shortest path problem requires careful analysis of its specific constraints. Understanding when to apply union-find versus Dijkstra, recognizing the importance of adjacency list handling for parallel edges, and implementing proper path comparison logic are essential skills for solving these types of competitive programming problems.