算法

  我写这篇文章的时候，可能是CSDN最早介绍D‘Esopo-Pape算法的博文了。这个算法其实并不难，但是这个算法在大多数情况下比Dijskstra算法和Bellman-Ford算法效率要高。这个算法是D’Esopo和Pape在1980年的论文中提出来的。
  这个算法几乎和Dijkstra完全一样，只是少数几个地方不同。Dijkstra算法是使用BFS搜索遍历，然后更新节点到源节点的距离。而D’Esopo-Pape算法大体上是BFS,但是在处理已经访问过的节点时使用DFS。不同点还在于Dijkstra使用的是优先队列，而D‘Esopo-Pape算法使用先进先出队列。
  其基本算法是BFS,如果遇到更短的距离，才将其加入队列。如果是已经加入过队列，把BFS改成DFS的方式。因为要更短的距离才加入队列，所以要将距离初始化为无限大，这和Dijkstra是一样的。下面我图解一下算法过程：

 初始化时都是负无穷的，如下图：


  后来发现了更短的到1的路径，所以更新，再从这个更短的出发，去找其他更短的路径，这就是为了放入队列头部，将BFS改成DFS的原因。

  下图是从1出发，发现到3的距离可以更短，如图：

  最终，最短距离计算结果如下：

Python实现

class WeightedEdge:

    def __init__(self, from_index, to_index, weight):
        self.__from_index = from_index
        self.__to_index = to_index
        self.__weight = weight

    @property
    def weight(self):
        return self.__weight

    @weight.setter
    def weight(self, value):
        self.__weight = value

    @property
    def from_index(self):
        return self.__from_index

    @from_index.setter
    def from_index(self, value):
        self.__from_index = value

    @property
    def to_index(self):
        return self.__to_index

    @to_index.setter
    def to_index(self, value):
        self.__to_index = value

    def __repr__(self):
        return f'{self.from_index} to {self.to_index} = {self.__weight}'

    def __str__(self):
        return f'{self.__from_index} to {self.__to_index} = {self.__weight}'


class WeightedGraph:
    def __init__(self, vertices, edges):
        self.__vertices = vertices
        self.__edges = edges
        self.__positions = None

    @property
    def vertices(self):
        return self.__vertices

    @vertices.setter
    def vertices(self, value):
        self.__vertices = value

    @property
    def edges(self):
        return self.__edges

    @edges.setter
    def edges(self, value):
        self.__edges = value
    @property
    def positions(self):
        return self.__positions

    @positions.setter
    def positions(self, value):
        self.__positions = value

    def to_dot(self):
        s = 'graph s {\n'
        for v in self.__vertices:
            s += f'"{v}";\n'
        for edges in self.__edges:
            for e in edges:
                if e.from_index > e.to_index:
                    s += f'\"{self.__vertices[e.from_index]}\"--"{self.__vertices[e.to_index]}"[label="{e.weight}"];\n'
        s += '}\n'
        return s

    def to_dot(self):
        s = 'graph s {\n'
        for v in self.__vertices:
            s += f'"{v}";\n'
        for edges in self.__edges:
            for e in edges:
                if e.from_index > e.to_index:
                    s += f'\"{self.__vertices[e.from_index]}\"--"{self.__vertices[e.to_index]}"[label="{e.weight}"];\n'
        s += '}\n'
        return s

    def to_distance_dot(self, src, distance):
        s = 'graph s {\n'
        if self.__positions is None:
            for v in self.__vertices:
                s += f'\t"{v}";\n'
        else:
            s += '''\tlayout = fdp
    node [shape = circle]\n'''
            for i, v in enumerate(self.__vertices):
                s += f'\t"{v}" [pos = "{self.__positions[i]}!"];\n'

        for edges in self.__edges:
            for e in edges:
                if e.from_index > e.to_index:
                    s += f'\t\"{self.__vertices[e.from_index]}\"--"{self.__vertices[e.to_index]}"[label="{e.weight}"];\n'
        s += '\n\tedge[style=dotted;color=salmon;fontcolor=salmon]\n\n'
        for i, x in enumerate(distance):
            if i != src:
                s += f'\t{src} -- {i}[label={x}]\n'
        s += '}\n'
        return s

    NOT_VISITED = 0
    VISITED = 1
    IN_QUEUE = 2

    def desopo_pape(self, source):
        queue = [source]
        distance = [float('inf') for _ in self.__vertices]
        distance[source] = 0
        colors = [WeightedGraph.NOT_VISITED for _ in self.__vertices]
        while len(queue) > 0:
            u = queue.pop(0)
            colors[u] = WeightedGraph.VISITED
            for edge in self.__edges[u]:
                v = edge.to_index
                new_distance = distance[u] + edge.weight
                if new_distance < distance[v]:
                    distance[v] = new_distance
                    if colors[v] == WeightedGraph.VISITED:
                        queue.append(v)
                        colors[v] = WeightedGraph.IN_QUEUE
                    elif colors[v] == WeightedGraph.NOT_VISITED:
                        queue.insert(0, v)
                        colors[v] = WeightedGraph.IN_QUEUE

        return distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

Python测试代码

import unittest

from com.youngthing.graph.desopo import WeightedEdge, WeightedGraph


class MyTestCase(unittest.TestCase):
    def test_shortes(self):
        vertex = [0, 1, 2, 3, 4]
        edges = [[WeightedEdge(0, 3, 1), WeightedEdge(0, 1, 6)],
                 [WeightedEdge(1, 0, 6), WeightedEdge(1, 3, 2), WeightedEdge(1, 2, 5), WeightedEdge(1, 4, 2)],
                 [WeightedEdge(2, 1, 5), WeightedEdge(2, 4, 5)],
                 [WeightedEdge(3, 0, 1), WeightedEdge(3, 1, 2), WeightedEdge(3, 4, 1)],
                 [WeightedEdge(4, 1, 2), WeightedEdge(4, 3, 1), WeightedEdge(4, 2, 5)],
                 ]
        graph = WeightedGraph(vertex, edges)
        graph.positions = ["0,0!", "1,0!", "2,1!", "0,1!", "1,1!"]
        print(graph.to_dot())
        distance = graph.desopo_pape(0)
        print(distance)


if __name__ == '__main__':
    unittest.main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

  测试结果：

[0, 3, 7, 1, 2]
1