The shortest path problem is one of network optimization problems. This paper considers a shortest path problem under the situation where lengths of arcs in a network include both uncertainty and randomness, and focuses on the case that the lengths of arcs are expressed by uncertain random variables. This paper presents a new type of model: relative entropy model of shortest path. By the definition of relative entropy of the uncertain random variables, relative entropy model of shortest path problem is proposed to find the shortest path which fully reflects uncertain and random information. This model is formulated to find a shortest path whose chance distribution minimizes the difference from the ideal one. A numerical example is given to illustrate the model’s effectiveness.

Abstract
I. Introduction
II. Preliminaries
    2.1. Uncertainty Theory
    2.2. Chance Theory
III. Shortest path problem
IV. Relative entropy model of shortest path
V. A numerical example
VI. A numerical example
References

• Gang SHI(School of Information Science and Engineering, Xinjiang University and Department of Computer Sciences, Tsinghua University)
• Yuhong SHENG(College of Mathematical and System Sciences, Xinjiang University and Department of Mathematical Sciences, Tsinghua University) Corresponding author
• Qing CUI(School of Information Science and Engineering, Xinjiang University)