Character segmentation has become a crucial step for mail address recognition in the automatic post mail sorting system. In this paper, a two-stage character segmentation algorithm according to the characteristics of handwritten mail address characters is proposed. In the simple segmentation stage, the block sequence is extracted from the mail address image using the structure-based methob, including projection profile analysis, connected components analysis and stroke cross number analysis. In the precise segmentation stage, all candidate segmentation paths are created by combining the neighboring blocks and represented with a candidate segmentation graph first. Then several optimal candidate paths are selected from the graph by dynamic programming searching based on recognition confidence. Finally the best segmentation path is determined by matching these paths with the known post address database. In the experiment on more than 500 real envelop images with the this approach, the correct sorting rate of address recognition is up to 79.46% and that of address-postcode integrated recognition is up to 96.26%.