| 无向图中严格第三短路问题的多项式时间算法 |
| |
| 引用本文： | 曾庆红.无向图中严格第三短路问题的多项式时间算法[J].云南民族学院学报(自然科学版),2014(1):58-61. |
| |
| 作者姓名： | 曾庆红 |
| |
| 作者单位： | 保山学院数学学院,云南保山678000 |
| |
| 基金项目： | 云南省应用基础研究计划项目（2013FD054）;保山学院校级科研教研项目（BBZ010） |
| |
| 摘 要： | 给定一个无向图G=（V，E；w；s，t），其中s，t是2个固定顶点，w：E→R^＋是边的长度函数．最短路是指所有路中长度最小者，次短路是指长度比最短路严格大的所有路中的最小者，严格第三短路是指长度比次短路严格大的所有路中的最小者．对正权重无向图中严格第三短路问题给出一个O（n^4）多项式时间算法．
|
| 关 键 词： | 最短路 次短路 严格第三短路 最小费用流 |
Polynomial time algorithm of the strictly third shortest path problem in the undirected graph |
| |
| ZENG Qing-hong.Polynomial time algorithm of the strictly third shortest path problem in the undirected graph[J].Journal of Yunnan University of The Nationalities(Natural Sciences Edition),2014(1):58-61. |
| |
| Authors: | ZENG Qing-hong |
| |
| Institution: | ZENG Qing-hong (Department of Mathematics, Baoshan University, Baoshan 678000, China) |
| |
| Abstract: | Given an undirected graph G = （ V, E ; w ; s, t）, where s and t are two fixed vertices, and w ： E→R^＋ is the length function. The shortest path is the path with the minimum length of all paths. A next - to - shortest path is a shorter path amongst all the paths having the length strictly greater than the length of the shortest path. A strict- ly third shortest path is the shortest path amongst all paths having the length strictly greater than the length of a next - to - shortest path. The paper proposes an O （ n^4 ） time algorithm to solve the strictly third shortest path problem in the undirected graph with positive weight. |
| |
| Keywords: | shortest path next -to -shortest path strictly third shortest path minimum cost flow |
| 本文献已被 维普 等数据库收录！ |
