求所有最小点成本最短路径算法

摘要

In this paper ,the shortest path problem with minimum node cost is studied .According to the characteristics of the shortest path problem with minimum node cost ,this paper modifies Dijkstra algorithm and puts forward a algorithm with time complexity O (2 + |E ||V |) and space complexity O (|V |E || + ) .And on this basis ,this paper makes full use of the characteristics of the problem ,puts forward a algorithm which is used to build up all shortest path problem with minimum node cost with time complex O |V |(w ) ,space complexity O (|V |E || + ) .%对点带成本的最短路径问题进行了研究。根据点带成本最短路径问题特点，对Dijkstra算法进行修改后给出一个时间复杂度为O（｜V｜2＋｜E｜）、空间复杂度为O（｜V｜＋｜E｜）的算法，并在此基础上充分利用问题的特点，给出一个时间复杂度为O （w｜V｜）、空间复杂度为O （｜V｜＋｜E｜）、构造所有点带成本最短路径的算法。