Bellman-Ford(边权可正可负) Bellman-Ford算法的迭代松弛操作,实际上就是按顶点距离s的层次,逐层生成这棵最短路径树的过程。 在对每条边进行1遍松弛的时候,生成了从s出发,层次至多为1的那些树枝。也就是说,找到了与s至多有1条边相联的那些顶点的最短路径;对每条边进行第2遍松弛的时候,生成了第2层次的树枝,就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含n-1 条边,所以,只需要循环n-1 次。 如果最短路存在,则一定不含环: 1.存在零环或正环,则去掉环路径不会变长 …

2014年7月13日 0条评论 0点热度 阅读全文