PKI是目前公认的保障网络安全的重要技术之一。当处于不同PKI信任域的实体，通过验证对方证书的有效性来建立信任时，需要进行证书路径处理的工作。证书路径处理由证书路径构建和证书路径验证组成。当前公开发表的证书路径构建算法主要有动态路径检测、ATV和证书路径表，这些算法均不能进行多路径处理，也没有对路径构建进行优化。 本文针对网状信任模型与桥CA信任模型进行域间证书验证，给出了这两种信任模型下的证书路径构建算法。算法采用分支限界的思想，使用证书路径树来表示证书路径信息，可以找到满足条件的最短证书路径，还可以解决多路径处理和回路检测的问题。 在网状信任模型中，对于更新周期不同的证书，本文采用了相应的处理方案。其中，对于更新周期长的证书，为了解决在路径处理时，取回证书和CRL、进行签名、状态的验证的耗时问题，先进行证书拓扑发现，再进行证书路径的构建；对于更新频繁的证书，在路径构建的过程中进行证书拓扑发现，只发现必要的拓扑信息，不必发现全部信任域的证书拓扑结构。 本文给出了PKI域间证书验证系统的体系结构，并针对网状信任模型与桥CA信任模型的不同特点，采用了剪枝、优先级排序以及缓存机制来提高证书路径处理的效率。