This　paper　proposes　the　optimal　shortest　path　set　problem　in　an　undirected　graph　,　in　which　some　vehicles　have　to　go　from　a　source　node　to　a　destination　node　.　However,　at　most　edges　in　the　graph　may　be　blocked　during　the　traveling.　The　goal　is　to　find　a　minimum　collection　of　paths　for　the　vehicles　before　they　start　off　to　assure　the　fastest　arrival　of　at　least　one　vehicle,　no　matter　which　edges　are　blocked.　We　consider　two　scenarios　for　this　problem.　In　the　first　scenario　with　,　we　propose　the　concept　of　common　replacement　path　and　design　the　Least-Overlap　Algorithm　to　find　the　common　replacement　path.　Based　on　this,　an　algorithm　to　compute　the　optimal　shortest　path　set　is　presented　and　its　time　complexity　is　proved　to　be　.　In　the　second　scenario　with　,　we　consider　the　case　where　the　blocked　edges　are　consecutive　ones　on　a　shortest　path　from　to　and　the　vertices　connecting　two　blocked　edges　are　also　blocked　(i.e.,　routes　passing　through　these　vertices　are　not　allowed),　and　an　algorithm　is　presented　to　compute　the　optimal　shortest　path　set　in　this　scenario　with　time　complexity　O(mn　+　k(2)n(2)　log　n).