论文部分内容阅读
1引言
20世纪中后期，随着计算机的出现和发展，图论的理论和应用研究得到广泛重视，图论作为一个数学分支的地位真正得到了确立。它与运筹学、离散数学、拓扑等
紧密结合，互辅互助，共同前进。同时，图论的应用已经深入到众多领域，比如GIS网络分析就是图论在地理信息领域的重要应用[10]，此外，在城市规划、电子导航、电子通讯、企业管理、工农业生产以及军事等方面也有着较为广泛的应用。
最短路径问题是图论中的一个典范问题[12]。主要研究成果有Dijkstra、Floyd等优秀算法[9，12]，Dijkstra还被认为是图论中的好算法[12]。但是值得注意的是，在理论上最优的算法不一定在实践中最优,仍然存在着某些局限性。比如网络特征可能时刻会发生变化,要求最短路径算法必须能够实时地自动更新。这类问题主要集中在交通网络的实时导航、通勤、调度和计算机互联网的数据传递路由等方面[7，8]。自然，人们目前的研究工作主要集中于算法实现的优化改进与应用方面，使得一个好的算法能够提高价值，解决实际生活更多、更复杂的问题。本文在对前人所做的改进算法综合基础上做了改进，使得一个算法能够解决多种局限性，在问题解决方面范围要更进一步。
2 新算法设计
2.1新算法描述及实现
2.1.1符号说明
若干符号分别定义为:
（1）G=（V，E）为简单赋权图，其中V为G的顶点集，E为G的边集。
（2）︱V︱=n为图G的顶点数。
（3）（u,v）表示边uv的权，一条路径的长度即为该路上各边的权和。
（4）N(u)表示无向图中含在S补集中的，与u相邻的顶点；N+(u)表示有向图中含在S补集中u的出邻域（与u相邻且边以u为起点的顶点集合）。
（5）r为迭代次数；K(v)r表示在第r轮迭代中顶点v的标号；K(v)表示顶点v的最终标号,该标号就是起点v1至v最短路径的长；ur表示在第r轮迭代中获得最终标号的顶点。
（6）S为已经获得最终标号的顶点集；T为标号集。
（7）Ui为得到两个最终标号Ki1与Ki2的第i个顶点，其中Ki1表示起点到ui的最短路长度,Ki2表示终点到ui的最短路长度；Hi=Ki1+Ki2 。
以下不妨称新算法为“扁担法”。之所以取名“扁担法”，实际上与扁担很类似，扁担是两头同时将重物挑起，而且前后重物的顺序交换一下，不影响人的承担能力。同样，所改进的“扁担法”在执行的过程中，也是从两个顶点同时以同样的做法进行。“扁担法”的主要原理是“变向”递归调用“改进标号法”。分别以所求最短路的两端顶点为起点实施 “改进标号法”，注意在实施的过程中要考虑是否为有向图。无向图时直接按李赉年的《求最短路径的“改进标号法”》中的算法进行。但如果是有向图，则在以终点为起点实施“改进标号法”时将有向边的方向朝相反方向考虑，即考虑的是顶点的入邻域，而不是出邻域。这样两端同时进行的话，必然会遇到有两个最终标号的顶点，这两个标号分别是到起点与终点的最短路长，相加的和即为两顶点间的一条较短路。随着过程的进行，不断遇到这样的顶点，直到全部顶点有这样两个标号，得到n个和，比较则可得到最小的和，即为所求。在前面所述的Dijkstra算法和“改进标号法”也适用于有向图的理论基础之上，又以递归调用为工具，无论是无向图还是有向图，算法完全正确。
2.1.2新算法描述
（1）分别以u与v为起点，两端同时使用“改进标号法”,过程参见李赉年的《求最短路径的“改进标号法”》。
（2）在某一轮迭代中进行到第一个特殊的顶点u1，这个顶点在以u为起点的过程中已经得到一个标号K11，但是在以v为起点的过程中又得到一个标号K12，即u到u1的最短路长度为K11，而v到u1的最短路长度为K12，那么在这个顶点旁记下H1=K11+K12，也就是说顶点u到顶点v的一条相对比较短的路的长度为H1。
（3）继续进行迭代，直到遇到第二个特殊顶点u2，重复（2），得到H2。
（4）如上依次进行。若r=n,则“改进标号法”结束。
（5）取H=min{H1,H2,H3,……,Hk,……,Hn}(k∈[1,n]),则H即为顶点u到顶点v的最短路的长度。这条最短路也可以由“改进标号法”的算法Ⅱ得到。
（6）如果要算出另外的最短路，则只需从{H1,H2,H3,……,Hk,……, Hn}(k∈[1,n])这个集合中找出与H等值的Hi；或者想找前N条最短路，则对上面集合重新按大小顺序排列即可得到。
2.1.3新算法实例
解计算的迭代过程见表一。表中顶点vj所在的列中，与第r行对应的xi表示在第r轮迭代中vj的标号是x，即K(vj)r=x，x的下标i表示在第i轮迭代中x从T中被删去，并且是vj的最终标号。符号“/”前面的数表示的是以点1为起点进行“改进标号法”所得的结果，后面的则是以点6为起点进行“改进标号法”所得的结果。
我们发现将计算的过程用以上这样的表格处理简单明了。最主要的是：由上表可以得到点1到点6的最短路的长度即为min{Hi}=8，并且最短路不经过点2，这些是可以从表上直接得到的。再应用改进标号法的算法2，可以得到两条最短路，分别为：1->4->3->6，1->4->5->6。当然，要排列两顶点之间的路长时，除了排列Hi外，更长的也可以找出来，只要将表格中“/”前后的数字分别相加，就可以得到另一些数据，也是两顶点之间的某条路的路长，排列之即可。
3新算法评价
与Dijkstra算法相比较，从以下几点实现的改进对本文的算法进行评价：
（1）首先是“改进标号法”的优势：
①Dijkstra算法在每一次迭代中对顶点v都要用min{L(v),L(ui)+w(uiv)}代替L(v),需要进行一次加法运算和一次比较,而“改进标号法”的算法I在每一次迭代中计算K(v)r只需进行一次加法,因而整个算法中减少了12n(n-1)次比较.
②本文算法的加法次数一般应少于Dijkstra算法的加法次数.
③由“改进标号法”中的算法Ⅱ可较方便的求出简单赋权图G中两顶点间的最短路径.
（2）在集合{H1,H2,H3,……,Hk,……,Hn}(k∈[1,n])中,当Hi=Hj=……=H（i,j∈[1,n]）时，解决了一个算法找多条最短路的问题。
（3）在上面集合中对各个元素Hi的比较，得到了不同大小的路径，也就找到了最短路，次短路，再次短路，……。
（4）第（2）点和第（3）点解决了路径的多重选择问题，若实际中有多项限制，则可以从中选择较好的路径，不一定会是最短的那条路径，使得新算法增加其适用性。
（5）当要找必须经过某顶点的最短路时，只需在表格中找到此顶点所在那列开始进行推导即可。
（6）本算法对于是否有向图无关紧要，两者都适合。
综上所述,本文的“扁担法”优于Dijkstra算法,成功解决了在算法评价中的前三点及最后一点的局限问题，因而是对原算法的一种改进。
4结束语
本算法继Dijkstra算法之后，在前人研究的两种算法基础之上，将其综合成一种新的算法，并添加自己的新的成分，成功解决了多个问题，克服了原有算法的不足之处，从而更具有适用性。所以在以后的学习生活中要注意学习方法的应用，以便更好、更快地解决更多的问题。
20世纪中后期，随着计算机的出现和发展，图论的理论和应用研究得到广泛重视，图论作为一个数学分支的地位真正得到了确立。它与运筹学、离散数学、拓扑等
紧密结合，互辅互助，共同前进。同时，图论的应用已经深入到众多领域，比如GIS网络分析就是图论在地理信息领域的重要应用[10]，此外，在城市规划、电子导航、电子通讯、企业管理、工农业生产以及军事等方面也有着较为广泛的应用。
最短路径问题是图论中的一个典范问题[12]。主要研究成果有Dijkstra、Floyd等优秀算法[9，12]，Dijkstra还被认为是图论中的好算法[12]。但是值得注意的是，在理论上最优的算法不一定在实践中最优,仍然存在着某些局限性。比如网络特征可能时刻会发生变化,要求最短路径算法必须能够实时地自动更新。这类问题主要集中在交通网络的实时导航、通勤、调度和计算机互联网的数据传递路由等方面[7，8]。自然，人们目前的研究工作主要集中于算法实现的优化改进与应用方面，使得一个好的算法能够提高价值，解决实际生活更多、更复杂的问题。本文在对前人所做的改进算法综合基础上做了改进，使得一个算法能够解决多种局限性，在问题解决方面范围要更进一步。
2 新算法设计
2.1新算法描述及实现
2.1.1符号说明
若干符号分别定义为:
（1）G=（V，E）为简单赋权图，其中V为G的顶点集，E为G的边集。
（2）︱V︱=n为图G的顶点数。
（3）（u,v）表示边uv的权，一条路径的长度即为该路上各边的权和。
（4）N(u)表示无向图中含在S补集中的，与u相邻的顶点；N+(u)表示有向图中含在S补集中u的出邻域（与u相邻且边以u为起点的顶点集合）。
（5）r为迭代次数；K(v)r表示在第r轮迭代中顶点v的标号；K(v)表示顶点v的最终标号,该标号就是起点v1至v最短路径的长；ur表示在第r轮迭代中获得最终标号的顶点。
（6）S为已经获得最终标号的顶点集；T为标号集。
（7）Ui为得到两个最终标号Ki1与Ki2的第i个顶点，其中Ki1表示起点到ui的最短路长度,Ki2表示终点到ui的最短路长度；Hi=Ki1+Ki2 。
以下不妨称新算法为“扁担法”。之所以取名“扁担法”，实际上与扁担很类似，扁担是两头同时将重物挑起，而且前后重物的顺序交换一下，不影响人的承担能力。同样，所改进的“扁担法”在执行的过程中，也是从两个顶点同时以同样的做法进行。“扁担法”的主要原理是“变向”递归调用“改进标号法”。分别以所求最短路的两端顶点为起点实施 “改进标号法”，注意在实施的过程中要考虑是否为有向图。无向图时直接按李赉年的《求最短路径的“改进标号法”》中的算法进行。但如果是有向图，则在以终点为起点实施“改进标号法”时将有向边的方向朝相反方向考虑，即考虑的是顶点的入邻域，而不是出邻域。这样两端同时进行的话，必然会遇到有两个最终标号的顶点，这两个标号分别是到起点与终点的最短路长，相加的和即为两顶点间的一条较短路。随着过程的进行，不断遇到这样的顶点，直到全部顶点有这样两个标号，得到n个和，比较则可得到最小的和，即为所求。在前面所述的Dijkstra算法和“改进标号法”也适用于有向图的理论基础之上，又以递归调用为工具，无论是无向图还是有向图，算法完全正确。
2.1.2新算法描述
（1）分别以u与v为起点，两端同时使用“改进标号法”,过程参见李赉年的《求最短路径的“改进标号法”》。
（2）在某一轮迭代中进行到第一个特殊的顶点u1，这个顶点在以u为起点的过程中已经得到一个标号K11，但是在以v为起点的过程中又得到一个标号K12，即u到u1的最短路长度为K11，而v到u1的最短路长度为K12，那么在这个顶点旁记下H1=K11+K12，也就是说顶点u到顶点v的一条相对比较短的路的长度为H1。
（3）继续进行迭代，直到遇到第二个特殊顶点u2，重复（2），得到H2。
（4）如上依次进行。若r=n,则“改进标号法”结束。
（5）取H=min{H1,H2,H3,……,Hk,……,Hn}(k∈[1,n]),则H即为顶点u到顶点v的最短路的长度。这条最短路也可以由“改进标号法”的算法Ⅱ得到。
（6）如果要算出另外的最短路，则只需从{H1,H2,H3,……,Hk,……, Hn}(k∈[1,n])这个集合中找出与H等值的Hi；或者想找前N条最短路，则对上面集合重新按大小顺序排列即可得到。
2.1.3新算法实例
解计算的迭代过程见表一。表中顶点vj所在的列中，与第r行对应的xi表示在第r轮迭代中vj的标号是x，即K(vj)r=x，x的下标i表示在第i轮迭代中x从T中被删去，并且是vj的最终标号。符号“/”前面的数表示的是以点1为起点进行“改进标号法”所得的结果，后面的则是以点6为起点进行“改进标号法”所得的结果。
我们发现将计算的过程用以上这样的表格处理简单明了。最主要的是：由上表可以得到点1到点6的最短路的长度即为min{Hi}=8，并且最短路不经过点2，这些是可以从表上直接得到的。再应用改进标号法的算法2，可以得到两条最短路，分别为：1->4->3->6，1->4->5->6。当然，要排列两顶点之间的路长时，除了排列Hi外，更长的也可以找出来，只要将表格中“/”前后的数字分别相加，就可以得到另一些数据，也是两顶点之间的某条路的路长，排列之即可。
3新算法评价
与Dijkstra算法相比较，从以下几点实现的改进对本文的算法进行评价：
（1）首先是“改进标号法”的优势：
①Dijkstra算法在每一次迭代中对顶点v都要用min{L(v),L(ui)+w(uiv)}代替L(v),需要进行一次加法运算和一次比较,而“改进标号法”的算法I在每一次迭代中计算K(v)r只需进行一次加法,因而整个算法中减少了12n(n-1)次比较.
②本文算法的加法次数一般应少于Dijkstra算法的加法次数.
③由“改进标号法”中的算法Ⅱ可较方便的求出简单赋权图G中两顶点间的最短路径.
（2）在集合{H1,H2,H3,……,Hk,……,Hn}(k∈[1,n])中,当Hi=Hj=……=H（i,j∈[1,n]）时，解决了一个算法找多条最短路的问题。
（3）在上面集合中对各个元素Hi的比较，得到了不同大小的路径，也就找到了最短路，次短路，再次短路，……。
（4）第（2）点和第（3）点解决了路径的多重选择问题，若实际中有多项限制，则可以从中选择较好的路径，不一定会是最短的那条路径，使得新算法增加其适用性。
（5）当要找必须经过某顶点的最短路时，只需在表格中找到此顶点所在那列开始进行推导即可。
（6）本算法对于是否有向图无关紧要，两者都适合。
综上所述,本文的“扁担法”优于Dijkstra算法,成功解决了在算法评价中的前三点及最后一点的局限问题，因而是对原算法的一种改进。
4结束语
本算法继Dijkstra算法之后，在前人研究的两种算法基础之上，将其综合成一种新的算法，并添加自己的新的成分，成功解决了多个问题，克服了原有算法的不足之处，从而更具有适用性。所以在以后的学习生活中要注意学习方法的应用，以便更好、更快地解决更多的问题。