A New Algorithm for Solving the Second Shortest Path in Directional Graph

作者：Su Zhixiong; Qi Jianxun

来源：CMSA Overall United Planning Symposium, 2010-11-05 to 2010-11-08.

• Graph theory
• the second shortest path
• character path algorithm
• CPM network planning

CPM network planning model is adapt to analyze schedule plan with strict immediate predecessor and successor restriction, viz, any activity could start only when its all immediate predecessor activities have finished, and using the model could find out the longest path in directional graph. According to the property of CPM network planning, and aiming at the shortest and the second shortest path problem, firstly, by analyzing properties of path length and floats in CPM network planning and extending the CPM network planning model, various CPM network planning model is founded which is corresponding to the CPM network model; secondly, by analyzing properties of the new model, new algorithm named character path algorithm is designed to solve the shortest and the second shortest path problem, and correctness of the algorithm is analyzed; and finally, illustration is used to validate the algorithm, which shows that the algprothm is effective and simple to solve the shortest and the second shortest path problem.

• 出版日期2010
• 单位华北电力大学