贪心算法——Dijkstra

亦凉 2022-01-20 03:19 276阅读 0赞

## 算法用途 ##

*  找出加权图中前往X的最短路径

> 并不单指距离，只要能转换成有向图并且边存在权重的情况都适用，当然边的权重不能存在负值

## 算法思想 ##

*  找最小花销的节点
 *  更新该节点邻居的最小花销
 *  重复上述过程直到遍历完图中全部的节点
 *  得出最终路径

## 算法实例 ##

Rama想拿乐谱换架钢琴，Alex愿意拿海报换Rama的乐谱，如果+5元还可以换Alex的唱片；Amy愿意拿出吉他或者架子鼓换海报或者唱片,唱片+15得吉他，唱片+20得架子鼓，海报+30得吉他，海报+35得架子鼓；Beethoven愿意拿出钢琴换Amy的吉他或者架子鼓，吉他+20得钢琴，架子鼓+10得钢琴；

## 解题思路 ##

### 1.将题目转换成图 ###

### 2.根据图生成3张表 ###

**第一张表记录节点间的相邻关系和权重，别名graph(方便后续论述)**

**第二张表记录图的起点到各个节点的最小开销表，别名cost**

目前仅知起点到唱片和海报的最小开销，其余节点需要计算得出

**第三张表记录各个节点在最小开销的情况下父节点的名称，别名parent**

因为目前仅知唱片和海报的最小开销，其余节点需在计算时保存父节点名称

### 3.结合上述三张表应用算法思想 ###

*  找最小花销的节点，即寻找cost表中开销数字最小的，那么我们找到了海报这个节点
 *  海报的邻居从graph表中可以知道为吉他和鼓，那么吉他的开销=30(graph\[海报\]\[吉他\])+0(cost\[乐谱\]\[海报\])=30；同理可得鼓的开销。那么它们是不是最小开销呢？因为我们的cost表是用来记录最小开销的，所以需要和cost中的值进行对比，如果小于cost表中的值即为最小开销。遍历cost表可知没有这两个节点，那么它们即为最小开销。
 *  更新cost表记录当前吉他和鼓的最小开销
 *  更新parent表记录当前吉他和鼓在取得最小开销时的父节点名称(目前是海报)

> 记得标记海报为已处理节点，这样再次从cost表中寻找最小开销节点时便不用考虑海报了

*  重复上述过程，寻找cost表开销最小的节点，找到了唱片，开销为5
 *  通过graph表得知唱片的邻居节点也是吉他和鼓，计算它们的开销分别为graph\[唱片\]\[吉他\]+cost\[乐谱\]\[唱片\]=20；graph\[唱片\]\[鼓\]+cost\[乐谱\]\[唱片\]=25；小于cost表中的30，35，所以它们是最小开销
 *  更新cost表，将吉他和鼓的最小开销更新为20，25
 *  更新parent表记录当前吉他和鼓在取得最小开销时的父节点名称(目前是唱片)

> 记得标记唱片为已处理节点，这样再次从cost表中寻找最小开销节点时便不用考虑唱片了

*  ....一直重复上述过程直到cost中的节点全部遍历完

> 根据上述过程我们了解到Dijkstra的每一步其实都是在更新cost表，记录各个节点的最小开销，最后一步一定是记录终点的最小开销。这种每一次过程其实也可以认为是在求最优解，所以它也是贪心算法的一种。

## 避雷 ##

*  **Dijkstra不适用于图上有负权边的情况**

> 我在上图中唱片与海报间加一条负权边

我们现在重复上述解题思路，生成三张表，graph表多一条记录graph\[唱片\]\[海报\]=-7，而cost表和parent表都是不变的！！！这就导致了问题，其实我们知道现在cost\[海报\]应该的等于-2才是最小开销而不是0，但是在最开始的cost表里仍然记录了0，然后我们开始计算:

*  遍历cost表中的最小开销，海报为0；找到邻居节点吉他和鼓，计算吉他和鼓的开销
 *  更新吉他和鼓的最小开销
 *  更新parent表记录当前吉他和鼓在取得最小开销时的父节点名称(目前是海报)
 *  标记海报为已处理节点！！！！！！到此海报节点已经被处理完毕了，它的最小开销被永远的记录为0，这与现实情况不符，而贪心算法后续的最优解一定是建立在前面已处理节点是最优解的基础上，所以后面的节点最小开销也会计算错误

PS：作者看的算法图解一书中提出Dijkstra不能用于有向环图，我一直不明白，自己模拟有环的数据也是能求出最短路径的，所以暂且认为Dijkstra是可以处理有向环图的。

## 实现源码 ##

package main
    
    import "fmt"
    
    func main(){
    	//定义graph字典
    	graph := map[string]map[string]int{
        "music":{
        "albumn":5,"post":0},
    					   "albumn":{
        "post":2,"guitar":15,"drum":20},
    					   "post":{
        "music":1,"guitar":30,"drum":35},
    					   "guitar":{
        "piano":20},
    					   "drum":{
        "piano":10},
    					  }
    	//定义开销字典
    	cost := map[string]int{
        "albumn":5,"post":0}
    	//定义存储父节点的字典
    	parent :=map[string]string{
        "albumn":"music","post":"music"}
    	//存储已经处理过的节点
    	handled := make(map[string]bool)
    	//找到最便宜节点,得到开销值 
    	smallestCost,smallestName := findSmallestCost(cost,handled)
    	
    	for smallestCost < 1000{
    		//找到邻居节点
    		neighbor := graph[smallestName]
    		//遍历邻居节点
    		for i,v := range neighbor{
    			if _, ok := cost[i]; ok {
    				newCost := v + cost[smallestName]//得到邻居新的开销
    				//如果小于之前的开销，更新开销，并更新parent节点信息
    				if(newCost<cost[i]){
    					cost[i] = newCost
    					parent[i] = smallestName
    				}
    			}else{
    				cost[i]=v+cost[smallestName]
    				parent[i] = smallestName
    			}
    		}
    		//将该节点加入到handled中
    		handled[smallestName]=true
            smallestCost,smallestName = findSmallestCost(cost,handled)//继续遍历其他节点
    	}
    	fmt.Printf("%+v\n",parent)
    }
    
    func findSmallestCost(cost map[string]int,handled map[string]bool) (a int,b string){
    	smallest := 1000
    	target :=""
    	for i,v := range cost{
    		if _,ok := handled[i];!ok{
    			if(v<smallest){
    				smallest = v
    				target=i
    			}
    		}
    	}
    	return smallest,target
    }
    复制代码