  This work addresses the Robust counterpart of the Shortest Path Problem
(RSPP) with a correlated uncertainty set. Since this problem is hard, a
heuristic approach, based on Frank-Wolfe's algorithm named Discrete Frank-Wolf
(DFW), has recently been proposed. The aim of this paper is to propose a
semi-definite programming relaxation for the RSPP that provides a lower bound
to validate approaches such as DFW Algorithm. The relaxed problem results from
a bidualization that is done {through} a reformulation of the RSPP into a
quadratic problem. Then the relaxed problem is solved using a sparse version of
Pierra's decomposition in a product space method. This validation method is
suitable for large size problems. The numerical experiments show that the gap
between the solutions obtained with the relaxed and the heuristic approaches is
relatively small.
