算法

狄克斯特拉算法

Posted by アライさん on 2019年10月22日

狄克斯特拉算法和旅行商问题的区别：
狄克斯特拉算法解决的问题，中间不需要经过指定的节点，并且有指定的起点和终点。
广度优先算法的线路没有权重。只计算最短路径，相当于权重都相同。

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
//已处理的节点
       private val processedMap = mutableMapOf<String, String>()
       //所有节点
       val graph = mutableMapOf<String, MutableMap<String,Int>>()
       graph["start"]=mutableMapOf()
       graph["start"]!!["b"] = 5
       graph["start"]!!["c"] = 0
       graph["b"]=mutableMapOf()
       graph["b"]!!["e"] = 15
       graph["b"]!!["d"] = 20
       graph["c"]=mutableMapOf()
       graph["c"]!!["d"] = 35
       graph["c"]!!["e"] = 30
       graph["d"]=mutableMapOf()
       graph["d"]!!["f"] = 10
       graph["e"]=mutableMapOf()
       graph["e"]!!["f"] = 20
       graph["f"]=mutableMapOf()

       //开销表
       val costsMap = mutableMapOf<String, Int>()
       costsMap["b"] = 5
       costsMap["c"] = 0
       costsMap["d"] = Int.MAX_VALUE
       costsMap["e"] = Int.MAX_VALUE
       costsMap["f"] = Int.MAX_VALUE


       //父节点情况
       val parentsMap = mutableMapOf<String, String>()
       parentsMap["c"]="a"
       parentsMap["b"]="a"
       parentsMap["d"]="Null"
       parentsMap["e"]="Null"
       parentsMap["f"]="Null"


       var node: String = findLowestCostNode(costsMap)?:""

       while (node.isNotEmpty()) {
           var cost = costsMap[node] ?: 0
           var neighbors = graph[node]

           neighbors?.forEach { (key, value) ->
               val newCost = cost.plus(neighbors[key] ?: 0)
               if (costsMap[key] ?: 0 > newCost) {
                   costsMap[key] = newCost
                   parentsMap[key] = node
               }
          }

           processedMap[node] = "true"
           node = findLowestCostNode(costsMap) ?: ""
       }

       System.out.println("开销变化 costsMap=".plus(costsMap))
       System.out.println("线路情况 parentsMap=".plus(parentsMap))


 //选出开销最小，并且没有处理过的节点
  private fun findLowestCostNode(costsMap: Map<String, Int>): String? {
      var lowestCost = Int.MAX_VALUE
      var lowestCostNode: String? = null

      costsMap.forEach { (key, value) ->
          //选出开销最小，并且没有处理过的节点
          if (value < lowestCost && processedMap[key].isNullOrEmpty()) {
              lowestCost = value
              lowestCostNode = key
          }
      }
      return lowestCostNode
  }



Tags
算法