算法

  我写这篇文章的时候，可能是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

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()

  测试结果：

[0, 3, 7, 1, 2]