This paper studies network routing under uncertain costs. We introduce the notion of regret and present methods to minimize it using data. Given a flow vector and a realization of the uncertainty, the regret experienced by a user on a particular path is the difference between the cost incurred on the path and the minimum cost across all paths connecting the same origin and destination. The network-wide regret is the cumulative regret experienced by all agents. We show that, for a fixed uncertainty, the total regret of all agents is a convex function provided the cost function of each path is affine and monotone. We provide two data-driven methods that minimize the expected value and a specified quantile of the total regret, respectively. Simulations compare our solutions to existing approaches of handling uncertainty in routing games.