不确定网络中的最短路径问题

The Shortest Path Problem of Uncertain Network

探索使用不确定理论中的期望值模型处理最短路径问题,将网络中有向边的权值描述为不确定变量,提出了利用99表表示的期望值简化最短路径通用模型,从而把模型直接转化为确定的最短路径问题模型,用传统方法如Dijkstra算法等即可求解.最后通过算例证明了模型的可行性与有效性.

In this paper,the expected value model of an uncertainty theory is introduced to deal with the shortest path problem.In the model,the weights of arcs of network are characterized as uncertain variables,and a simplified shortest path general model expressed by 99-table is put forward.Therefore,the model is transformed to the certain shortest path problem and can be solved by the traditional algorithm such as Dijkstra.At last,an example is to illustrate the effectiveness and feasibility of the model.