算法51-Dijkstra算法

迪杰斯特拉（dijkstra）算法是单源最短路径问题的求解方法。单源最短路径就在给出一个固定网络，指定一个原点s，一个目标点e，求这两个点之间的最短路径。举个栗子来理解一下。

假定输入的图如下：
graph := [][]int{}
tmp:=[]int{0, 7, 9, 0, 0, 14}
tmp1:=[]int{7, 0, 10, 15, 0, 0}
tmp2:=[]int{9, 10, 0, 11, 0, 2}
tmp3:=[]int{0, 15, 11, 0, 6, 0}
tmp5:=[]int{0, 0, 0, 6, 0, 9}
tmp6:=[]int{14, 0, 2, 0, 9, 0}

表示0-5点到其他点的距离，数值为0表示不可到达

先说单向的情况，
1 定义一个数组，对应的index上的值表示0点到每一点的距离，将其初始为Maxint，小于它则更新，
2 用一个数组对应记录这个点是否被lock，表示单向，只能往前，不能再回退回去更新已经算过的值
3 这样每一点的值则等于 Min（0到当前点的最小值（已经算出来的值）+到下一点的距离）

如果路径是双向的，可以鞥新已经计算过的点是值，就不需要lock已经计算过的点

代码：

package  main

import(
	"fmt"
	"math"
)
//有序，路径是有序的
func dijkstra(graph [][]int,start int){
	mindistance:=make(map[int]int)
	mindistance[start]=0
	for i :=1;i<len(graph);i++{
		mindistance[i]=math.MaxInt16

	}
	lock := make([]int,len(graph))

	// lock:=[]int{0,len(graph)}
	fmt.Println(lock)

	for i :=0;i<len(graph);i++{
		for j:=0;j<len(graph[0]);j++{
			if lock[j]!=1 && graph[i][j] >0 {
				mindistance[j]=int(math.Min(float64(mindistance[i]+ graph[i][j]),float64(mindistance[j])))
				lock[i]=1
			}
		}
	}
	fmt.Println(mindistance)
}


//无序，边是无序
func dijkstra1(graph [][]int,start int){
	mindistance:=make(map[int]int)
	mindistance[start]=0
	for i :=1;i<len(graph);i++{
		mindistance[i]=math.MaxInt16

	}
	// lock := make([]int,len(graph))

	// lock:=[]int{0,len(graph)}
	// fmt.Println(lock)

	for i :=0;i<len(graph);i++{
		for j:=0;j<len(graph[0]);j++{
			if  graph[i][j] >0 {
				mindistance[j]=int(math.Min(float64(mindistance[i]+ graph[i][j]),float64(mindistance[j])))
			}
		}
	}
	fmt.Println(mindistance)
}
func main(){
	
	graph := [][]int{}
	tmp:=[]int{0, 7, 9,  0,  0, 14}
	tmp1:=[]int{7, 0, 10, 15, 0, 0}
	tmp2:=[]int{9, 10, 0, 11, 0, 2}
	tmp3:=[]int{0, 15, 11, 0, 6, 0}
	tmp5:=[]int{0, 0,  0,  6, 0, 9}
	tmp6:=[]int{14, 0, 2, 0,  9, 0}




	graph=append(graph,tmp)
	graph=append(graph,tmp1)
	graph=append(graph,tmp2)
	graph=append(graph,tmp3)
	graph=append(graph,tmp5)
	graph=append(graph,tmp6)
	dijkstra(graph,0)
	dijkstra1(graph,0)

}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

结果：

map[0:0 1:7 2:9 3:20 4:26 5:11]
map[0:0 1:7 2:9 3:20 4:20 5:11]

1
2
3

总结：

1，有序就锁住计算过的点，无序就不用锁
2，注意是0到当前点的值+当前点到下一点的值