dijkstra最短路径算法步骤_(超多动图)最短路径Dijkstra详解算法-看不懂算我输

作者：从前慢现在也慢 | 2024-04-18 06:02:28

踩

dijkstra算法步骤

Hello, 我回来继续更新啦。那么今天说什么话题呢? 今天不做题，来把之前挖的坑给它填补一下, 不知道小伙伴们还记不记得上一次挖的坑一篇文章带你了解【图】的结构及相关【算法】就是这一篇文章中，要在接下来教大家什么是 「最短路径Dijkstra算法」, 那么经过这么多天的忙碌,终于有时间把这个写下来了

前言

大家都知道, 在图的遍历「BFS」中我们是使用队列进行图的遍历对吧，其实在队列里面有一个很明显的特点不知道大家有没有发现其实每个顶点出队后，与在队列中的元素距离都是线性比例的。就是相差1条边,2条边,3条边这样子的。

那么我们知道,「A->D」的最短路径可以是「ABD 或者 ACD」，那是因为在这个图上没有加权选项在其中，那么如果有权值的话，不能说某条边就是最短的了，我们来看个例子

如果图长这个样子呢? 还是「ABD 或 ACD」最短吗? 不是了把, 最短的就是「ACBD」这条路径了

优先队列

队列大家都很清楚了, 就是先进先出的一个机制，很简单，那么什么是「优先队列」呢?,简单而言就是加权的队列, 优先队列里面除了保存一个「节点」以外，还会保存一个「节点的权值」 比方说,从「A->B」的距离是「5」 那么入队的时候，就不再是把「B」加入队列中，而是「B,5」这样的形式入队列，我们来举个例子

如果说，队列中只有一个元素「B,5」的话，那么它就在队列的对头，如果说下一个元素「C,1」进来的时候会发生什么事呢?

会对队列内的元素权重值进行一次排序

也就是每一次的插入, 都会确保队头部分的元素是整个队列中最小的,也正是因为这个实现了该算法的核心。

用Go语言实现优先队列还必须实现以下几个接口

Len()int
Swap(i,j int)
Less(i, j) bool
Push(x interface{})
Pop() interface{}

Dijkstra算法

终于到了今天的重头戏，算法的核心讲解了，我们先来看一下这个算法需要用到哪些数据结构

邻接表


ans := make(map[string]map[string]int)
 ans["A"] =  map[string]int{"B":5,"C":1}
 ans["B"] = map[string]int{"A":5, "C":2, "D":1}
 ans["C"] = map[string]int{"A":1, "B":2, "D":4, "E":8}
 ans["D"] = map[string]int{"B":1, "C":4, "D":3, "F":6}
 ans["E"] = map[string]int{"C":8, "D":3}
 ans["F"] = map[string]int{"D":6}

简单而言就是先定义一个图的列表其实就是这个样子

初始化工作


func initGraph(graph map[string]map[string]int, start string,dist *map[string]int){
 for w ,_ := range graph{
  if w != start{
   (*dist)[w] = 100000000000
  }
 }
}

我们要先初始化这些节点的距离为无穷大，才能做最小值的匹配判断。只要邻接表中的元素不是首元素，则把他的距离设置为无穷大, 设置完以后的数据结构应该长这个样子/ 「B:100000000,C:100000000,D:10000000....」 这样的结构

父节点

我们用一个字典来记录某个节点的父节点


parent := make(map[string]string) //記錄某個節點的上一個節點
parent[start] = "None"

比方说，我们要记录 C 的父节点是A, 因为「A->C的距离为1，且是当前最短的路径」我们就把A写在「KeyC的value里面」变成以下这张图。并且我们把「初始节点的父节点为None」

处理节点

也是用一个字典来记录某个已经被处理过的顶点

isTouch := make(map[string]int) //看到過某個點的集合

我们知道, A是起始的顶点，它已经被处理过了, 并且把与A相邻的顶点也加入到优先队列中,因此我们要把处理完的顶点打个记号，这个记号就是打在「isTouch」里面

标记「顶点A为1」说明该顶点已经被访问过了

顶点距离

distance := make(map[string]int) //記錄頂點之間的距離

从上面的图中,我们知道「A->C」的距离是1, 且该距离是最短的距离,因此我们要在「distance」中把「A->C的距离标记为1」

优先队列初始化


pqueue := &priorityQueue.NodeSlice{}//優先隊列
node := priorityQueue.Node{start, 0} //初始化起始节点
 
heap.Init(pqueue)//初始化優先隊列
heap.Push(pqueue, node)//將首節點添加進去

我们先初始化一个队列叫做「pqueue」, 代码中的结构体,我之后会贴在Github上，如果有需要可以去github中查看。然后在把起始节点初始化后放入优先队列中，完成上面一系列的初始化操作以后，我们终于可以进入正题讲解算法的核心了

核心算法

我们先来看一下算法的核心部分，然后我们再一步步拆解它，解释其中的意思


for pqueue.Len() > 0 {//队列不为空的时候
  vertNode := heap.Pop(pqueue).(priorityQueue.Node) //彈出第一個
  vert:=vertNode.Ver //頂點名稱
  length:=vertNode.Length //到该頂點的距離
    
  isTouch[vert] = 1 //从队列拿出來以後才標記成為已經處理過了
  nodes := graph[vert] //此處拿出來的是一個map 像這樣map[B:5 C:1]
    
  for w, _ := range nodes {//遍历其中的nodes, 因为该nodes为一个顶点和权值的数组
   if _, ok := isTouch[w]; !ok {// 如果该元素并未被标记过已处理的
    if length + graph[vert][w] < distance[w]{ //因为刚开始的距离为无穷大
        
     tmpNode := priorityQueue.Node{w,length + graph[vert][w]}//新建一个节点,
     heap.Push(pqueue, tmpNode) //加入到队列中
     parent[w] = vert //标记该节点的父节点
     distance[w] = length + graph[vert][w] //标记去到该节点的距离
 
   }
  }
 }
}