In　this　paper,　an　integrated　approach　combining　offline　pre-computation　of　optimal　candidate　paths　with　online　path　retrieval　and　dynamic　adaptation　is　proposed　for　a　dynamic　navigation　system　in　a　centralized　system　architecture.　Based　on　a　static　traffic　data　file,　a　partially　disjoint　candidate　path　set　is　constructed　prior　to　the　trip　using　a　heuristic　link　weight　increment　method.　This　method　satisfies　reasonable　path　constraints　that　meet　the　drivers＇　preferences　as　well　as　alternative　path　constraints　that　limit　the　joint　failure　probability　for　candidate　paths.　The　characteristics　of　the　proposed　algorithm　are　the　following:　1)　the　response　time　for　online　navigation　demand　is　nearly　linear　with　network　size　and　less　dependent　on　system　load;　2)　the　veracity　of　the　pre-trip　route　plan　based　on　the　static　data　file　is　improved　by　taking　travel　time　reliability　into　account;　and　3)　system　optimization　can　be　approximated　without　sacrificing　driver　preferences.　The　algorithm　is　tested　on　randomly　generated　road　networks　and　the　numerical　results　show　the　efficiency　of　the　approach.　©　2005　IEEE.