Data Procurement for Shortest Paths on Random Graphs

Abstract

While Dijkstra's algorithm finds the shortest path between two nodes on a graph with known edge weights, we approach the shortest paths problem for graphs with random edge weights described by known probability distributions. We introduce the idea of a budget of size k which allows us to replace k random edges with numbers drawn from the edges' distributions. Our problem is to determine which edges to replace with random realizations to minimize the minimum expected path distance across all paths between two nodes, given the realized edge weights. We evaluate several greedy heuristics, with different lookaheads, for choosing edges. We also prove that any greedy heuristic with lookahead less than the budget has no finite approximation ratio to the optimal policy.