We propose Node Path Vector (NPV) to capture complete shortest routing information for a Generalized Hypercube System. We also introduce the concept of relay node technique to reduce the computation complexity in obtaining NPV. Optimal Fault-Tolerant Routing Scheme (OFTRS) is further proposed to derive an optimal or sub-optimal routing path for any communication pair in a Generalized Hypercube System. Compared to previous work, OFTRS will not omit any routing information for optimal and sub-optimal path even in a generalized hypercube system with large number of faulty nodes and links while the previous schemes can potentially omit 60% routing paths. Thus it considerably improves the quality of fault-tolerant routing. In addition, our proposed scheme is distributed and relying only on non-faulty neighboring nodes, thus it has high applicability. Finally, the algorithm guarantees to route through the optimal or sub-optimal path as long as a path between the source-destination pair exists.