迪杰斯特拉算法

简介

迪杰斯特拉算法的是用于图搜索的一种算法，其作用是图中搜索出单源最短路径。单源最短路径问题是一个给定起始点和目标点，在图中搜索出由起始点到目标点最短路径问题。

核心思想

迪杰斯特拉算法是贪心算法。表现在于每次只扩展累计代价值最小的节点。

贪心算法的优缺点

• 优点：逻辑正确的贪心算法有复杂度低、代码量小、运行效率高、空间复杂度低等优点
• 缺点：贪心算法的缺点表现在”非完美性“，通常很难找到一个简单可行并且保证正确的贪心思路，即使我们找到一个看上去很正确的贪心思路，也需要严格的正确性证明。这往往给我们直接使用贪心算法带来了巨大的困难。往往不能保证求得的最后解是最佳的；同时贪心算法也不能用来求最大或最小解的问题，只能求满足某些约束条件的可行解的范围。

运行过程

1. 初始化：在开始时，将起始节点的距离设为0，将所有其他节点的距离设为无穷大。这是因为在开始时，只知道起始节点的距离，而不知道其他节点的距离。
2. 选择代价值最低的未访问：然后，我们从未访问的节点中选择一个距离最近的节点。在第一次迭代中，这将是起始节点，因为其距离是0。
3. 更新邻居节点的距离：查看所选节点的每个邻居。如果通过当前节点到达邻居节点的距离小于已知的最短距离，就更新邻居节点的最短距离。并记录下如何到这个邻居节点。
4. 标记为已访问节点：当查看了一个节点的所有邻居并更新了其距离后，将这个节点标记为已访问。已访问的节点将不再被考虑。
5. 重复：重复步骤2和3，直到所有可达的节点都被访问。

算法的关键在于每一次决策都做出了”贪心选择“，即只扩展代价值最小的节点，尽管着这种决策并非全局最优，但确实能够找到最小路径。

迪杰斯特拉算法只适用于权重非负的图，如果一个图中的某些边权重是负值，那可能找不到最短路径，这种情况就要使用Bellman-Ford或Floyd-Warshall

代码

伪代码

function Dijkstra(Graph, source):
 
    create vertex set Q

    for each vertex v in Graph:            
        distance[v] ← INFINITY                 
        previous[v] ← UNDEFINED                
        add v to Q                     
    distance[source] ← 0                       
 
    while Q is not empty:
        u ← vertex in Q with min distance[u]   
                                              
        remove u from Q 
       
        for each neighbor of u:           
            alt ← distance[u] + length(u, neighbor)
           
            if alt < distance[neighbor]:              
                distance[neighbor] ← alt
                previous[neighbor] ← u
 
    return distance[], previous[]

• Graph是一个图，其中包含了所有的节点和边的信息。
• source是源节点，即从哪个节点开始计算。
• distance[v]是从源节点到节点v的最短路径长度。
• previous[v]是在最短路径上，节点v的前一个节点。
• Q是一个集合，包含了所有待处理的节点。
• u是当前正在处理的节点。
• neighbor是u的邻居节点。
• alt是从源节点到邻居节点的候选最短路径长度。

参考：贪心算法综述_贪心算法的优缺点-CSDN博客

Python代码

def dijkstra(graph, start, target):
	queue_from_start = []
	heapq.heappush(queue_from_start, (0.0, start))
	distances = {node: flaot("inf") for node in graph}
	parents_of_start = {start:None}
	close_of_start = set()
	distances[start] = 0.0

	while queue_from_start:
		cur_dist, cur_node = heapq.heappop(queue_from_start)
		if cur_node is target:
			return traversal(target, parents_of_start)
		close_of_start.add(cur_node)
		for adjacent, weight in graph.items()
			if adjacent in close_of_start:
				continue
			dist_temp = distances[cur_node] + weight{"weights"}
			if dist_temp < distances[adjacent]:
				distances[adjacent] = dist_temp
				parents_of_start[adjacent] = cur_node
				heapq.heappush(queue_from_start, (dist_temp, adjacent))

def traversal(T,pred):
    path = []
    while T is not None:
        path.append(T)
        T = pred[T]
    return path[::-1]