The on-line shortest path problem is considered in a network where the arc costs are not known for decision makers. They are revealed in on-line manner and the on-line made decisions do not changed or rejected. An on-line method is proposed based on the primal-dual algorithm and its competitive analysis is obtained as 2/3 L, where L is the longest distance between the nodes. Two kinds of on-line decision policies are applied to minimize the infeasibility of the dual problem. The numerical results show that the local policy performs better than the global policy.
