This paper focuses on one of DTN’s deterministic routing algorithms—ED (Earliest-Delivery) and makes an analysis of its calculation of the delay cost function. To select the accurate time of routing decision-making and optimize the calculation of delay cost, a link connection state table is employed. On this basis, the transmission delay and rules of node-link connection are taken into account. Experimental results show that the improved ED can effectively reduce the delay and improve routing success rate.