首先我们根据我随意设定的一个路径建立一个字典

path = {
    "A":{"B", "C"},
    "B":{"A", "D", "E"},
    "C":{"A", "D"},
    "D":{"C", "E", "B", "F"},
    "E":{"B", "D"},
    "F":{"D"}
}

BFS需要用到队列我直接使用的Python的双端队列，广度优先搜索就是一层一层的搜索每搜索一层就把下一层加到队列里面。

def BFS(path, s):
    parent = {s:None}
    seen = set()
    seen.add(s)
    q = deque()
    q.append(s)
    while q:
        node = q.popleft()
        for w in path[node]:
            if w not in seen:
                seen.add(w)
                parent[w] = node
                q.append(w)
        print(node)
    return parent

DFS就是把队列改成栈就行了，深度优先搜索就是先一条路走到黑，发现走不了再退回来换条路走。代码就是把队列换成栈。

def DFS(path, s):
    parent = {s:None}
    seen = set()
    seen.add(s)
    q = deque()
    q.append(s)
    while q:
        node = q.pop()
        for w in path[node]:
            if w not in seen:
                seen.add(w)
                parent[w] = node
                q.append(w)
        print(node)

现在我们给每条路径加上一个权值。

 

这样我们的路径就要加上一个权值了。

path = {
    "A":{"B":3, "C":2},
    "B":{"A":3, "D":2, "E":1},
    "C":{"A":2, "D":4},
    "D":{"C":4, "E":3, "B":2, "F":3},
    "E":{"B":1, "D":4},
    "F":{"D":3}
}
def init_distance(path, s):
    distance = {}
    for w in path:
        if w == s:
            distance[w] = 0
        else:
            distance[w] = float('inf')
    return distance

def dijkstra(path, s):
    parent = {s:None}
    seen = set()
    pq = []
    heapq.heappush(pq, (0, s))
    distance = init_distance(path, s)
    while pq:
        dist, vertex = heapq.heappop(pq)
        seen.add(vertex)
        for w in path[vertex]:
            if w not in seen and dist + path[w][vertex] < distance[w]:
                distance[w] = dist + path[w][vertex]
                parent[w] = vertex
                heapq.heappush(pq, (distance[w], w))
    return parent, distance
parent, distance = dijkstra(path, "A")
print(distance)
print(parent)
v = "F"
while v:
    print(v)
    v = parent[v]