python 中的等价多径 Dijkstra 算法

Question

使用此处推荐的 python 食谱：

http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/

和

http://code.activestate.com/recipes/117228-priority-dictionary/

并使用下图作为输入：

 graph_2  = {
    'R1':{'R2':5,'R3':5},
    'R2':{'R1':5,'R4':5},
    'R3':{'R1':5,'R4':5},
    'R4':{'R2':5,'R3':5},
}

我正在尝试获取 R1 和 R4 之间的所有最短路径。但是，我只得到一条最短路径 (R1-R2-R4)，而不是 (R1-R3-R4)。我需要模拟 ECMP（例如 OSPF）。我需要的是函数 shortestPath returns 所有最短路径（即 [[R1-R2-R4],[R1-R3-R4]]）在等价多路径的情况下（如顶部的 graph_2 ) 并且在单路径的情况下只有最短路径，例如：

  graph_3  = {
    'R1':{'R2':5,'R3':5},
    'R2':{'R1':5,'R4':5},
    'R3':{'R1':5,'R4':10},
    'R4':{'R2':5,'R3':5},
}

我修改了 Dijkstra 函数中的代码：

from priodict import priorityDictionary

graph_2  = {

'R1':{'R2':5,'R3':5},
'R2':{'R1':5,'R4':5},
'R3':{'R1':5,'R4':5},
'R4':{'R2':5,'R3':5},
}



def Dijkstra(G,start,end=None):

    D = {}  # dictionary of final distances
    P = {}  # dictionary of predecessors
    Q = priorityDictionary()   # est.dist. of non-final vert.
    Q[start] = 0
    for v in Q:
        D[v] = Q[v]
        if v == end: break

        for w in G[v]:
            vwLength = D[v] + G[v][w]

            if w in D:
                if vwLength < D[w]:
                    raise ValueError, \
            elif w not in Q or vwLength < Q[w]:
                Q[w] = vwLength
                P[w] = [v]
            elif  w not in Q or vwLength == Q[w]: <---adding this part
                Q[w] = vwLength
                P[w] += [v]

    return (D,P)

def shortestPath(G,start,end):
    D,P = Dijkstra(G,start,end)
    print D,P
    Path = []
    while 1:
        Path.append(end)
        print end
        if end == start: break
        end = P[end]
    Path.reverse()
    return Path

print shortestPath(graph_2,'R1','R4')

我得到以下输出和错误：

{'R4': 10, 'R1': 0, 'R2': 5, 'R3': 5} {'R4': ['R2', 'R3'], 'R2': ['R1'], 'R3': ['R1']}

Traceback (most recent call last):
File "next-hop-resolver.py", line 194, in <module>
print shortestPath(graph_2,'R1','R4')
File "next-hop-resolver.py", line 172, in shortestPath
end = P[end]
TypeError: unhashable type: 'list'

我想使用 graph_2 得到的是：

[['R1', 'R2', 'R4'], ['R1', 'R3', 'R4']]

并使用 graph_3:

[['R1', 'R2', 'R4']]

如果我按原样执行代码，即不进行任何类型的代码修改，无论我使用 graph_2 还是 graph_3:

，我都会得到以下结果

[['R1', 'R2', 'R4']]

即始终是最短路径，即使有多条路径。

我知道列表不能成为字典中的键，但老实说我坚持这一点，所以非常欢迎任何帮助

Answer 1

分析

感谢您提供可运行的代码。您还没有解释您的设计，但功能问题很清楚：P 负责返回当前路径上任何给定节点的前任节点。由于一条路径是严格线性的，因此只能有一个前驱。 while 循环 shortestPath 依赖于此。

但是，您返回的 P 列出了 two 个 R4 沿当前路径的前辈，然后您立即尝试用它们同时索引 P。你不能那样做；你必须单独处理每条路径。

解决方案

简单地修复你的代码无异于为你做功课；即不酷。既然你已经走到这一步了，我建议你改变 shortestPath 中的循环以通过多个路径工作。从处理每个个返回值的想法开始，依次，一次处理一个：

while True:
    for node in end:
        # continue with single-path code

编码说明

是的，我将循环条件形式 1 更改为 True。您使用的食谱似乎是由从 C 或其他早期第三代语言翻译过来的人编写的，没有学习当今的编码改进。单字母变量名、大写字母等是当今程序员不合标准的习惯。（我不得不重新学习一些，我自己。）

要了解您的工作目标，请参阅 PEP-8。

Answer 2

终于，我想我得到了我要找的东西:)

这是最终代码

from priodict import priorityDictionary
from collections import defaultdict
from collections import OrderedDict
import sys
graph_2  = {

'R1':{'R2':5,'R3':5},
'R2':{'R1':5,'R4':5},
'R3':{'R1':5,'R4':5},
'R4':{'R2':5,'R3':5,'R5':5},
'R5':{'R4':5}

}

graph_3 = {

'192.168.255.1':{'192.168.255.2':10,'192.168.255.3':10},
'192.168.255.2':{'192.168.255.1':10,'192.168.255.3':50},
'192.168.255.3':{'192.168.255.1':20,'192.168.255.2':50},
'192.168.255.4':{'192.168.255.3':20},
'192.168.255.3':{'192.168.255.4':20}
}

graph_4 = {
'R1':{'R2':5},
'R2':{'R1':5},
'R2':{'R3':5},
'R3':{'R2':5},
'R3':{'R4':5},
'R4':{'R3':5}
}

graph_5 = {

'A':{'B':5,'C':10,'E':2},
'B':{'A':5,'C':5},
'C':{'B':5,'A':10,'E':8,'D':4},
'D':{'C':4,'E':5},
'E':{'A':2,'D':5,'C':8}

}

def Dijkstra(g,start,end=None):

    d = {}  # dictionary of final distances
    p = {}  # dictionary of predecessors
    q = priorityDictionary()   # est.dist. of non-final vert.
    q[start] = 0
    for v in q:
        d[v] = q[v]
        if v == end: break      
        for w in g[v]:
            vwLength = d[v] + g[v][w]
            if w in d:
                if vwLength < d[w]:
                    raise ValueError
            elif w not in q or vwLength < q[w]:
                q[w] = vwLength
                p[w] = [v]
            elif  w not in q or vwLength == q[w]:
                q[w] = vwLength
                p[w] += [v] 
    return (d,p)        

def shortestPath(g,start,end):

    d,p = Dijkstra(g,start,end)
    path = [[end]]
    while True:
        if len(p[end]) > 1:
            path.append(p[end])
            for node in p[end]:
                if node != start:
                    if ''.join(p[end]) == start: break
                    end = node
        path.append(p[end])
        if ''.join(p[end]) == start: break
        for node in p[end]:
            if node == start: break
            end = node  
    return path[::-1]


print shortestPath(graph_2,'R1','R5')
print shortestPath(graph_3,'192.168.255.1','192.168.255.2')
print shortestPath(graph_4,'R1','R4')
print shortestPath(graph_5,'A','C')

以及每张图的输出：

[['R1'], ['R2', 'R3'], ['R4'], ['R5']]
[['192.168.255.1'], ['192.168.255.2']]
[['R1'], ['R2'], ['R3'], ['R4']]
[['A'], ['A', 'E', 'B'], ['C']]

python 中的等价多径 Dijkstra 算法

Equal cost multipath Dijkstra's Algorithm in python

python

algorithm

dijkstra