This paper presents a new concept Optimal Path Matrices for fault-tolerant routing on hypercube multicomputers. Optimal Path Matrices (OPMs) stored on each node of a hypercube keep faulty information and indicate whether there is an optimal path from the node to a destination. Two fault-tolerant routing algorithms based on Optimal Path Matrices are proposed to maintain the matrices and route messages from sources to destinations. One is a routing algorithm based on OPMs, which are filled with pre-collected information through information exchange between neighbors. It can easily establish a path for a message. And the length of the path is no greater than the hamming distance between the source and the destination of the message plus two. The other is a modified depth-first search algorithm, which adopts a dynamically learning strategy to fill OPMs during normal message transmission and can find almost all optimal paths. The memory overhead is n2 words on each node of an n-dimensional hypercube.