For the separable convex cost flow problem, we consider the problem of determining tolerance set for each arc cost function. For a given optimal flow x , a valid perturbation of c i j ( x ) is a convex function that can be substituted for c i j ( x ) in the total cost function without violating the optimality of x . Tolerance set for an a r c ( i , j ) is the collection of all valid perturbations of c i j ( x ) . We characterize the tolerance set for each a r c ( i , j ) in terms of nonsingleton shortest distances between nodes i and j . We also give an efficient algorithm to compute the nonsingleton shortest distances between all pairs of nodes in O ( n 3 ) time where n denotes the number of nodes in the given graph.