Dijkstras Algorithm

学习Dijkstras算法

一、简介

Dijkstras算法是典型的单源最短路径算法。用于计算一个节点到其它所有节点的最短路经。主要特点是以起点为中心向外层层扩展，直到扩展到终点为止。即解决有权重的有向图单源最短路经的问题。

该算法有一个艰制就是：所有边的权重都必需为非负数。

问题描述：在无向图G=(V,E)中，假设每条边E[I]的长度为W[i]，找到由顶点V0到其余各点的最短路经。

二、算法思想

Dijkstras算法是思想是贪婪算法；

1。首先我们从起点开始，更新起点能到达的相邻点的路经距离；

2。其次，我们在乘余点中找到离起点最近的一个点，并更新该点所有直接相邻点到起点的路程距离；

3。接下来，我们一直重复上一步，始终在剩余点中找一个距离起点最近的一个点，并更新其所有邻居点到起点的距离；

4。最后，遍历完所有顶部，完成计算；

三、图解过程

参考

四、代码实现

package _Algorithm.Dijkstra

import java.util.*
import kotlin.collections.HashMap

class TestDijkstra {

    /**
     * id: 我们要知道这个顶点是谁
     * neighbors: 这个顶点能到达的邻居有哪些,并到达这些邻居的路经有多长
     * predecessor: 上一个顶点
     * distance: 该点到起始点的距离
     * */
    class Vertex constructor(id_: Char) {
        var id: Char? = null
        var neighbors = HashMap<Vertex, Int>()
        var predecessor: Vertex? = null
        var distance: Int = Int.MAX_VALUE

        init {
            this.id = id_
        }

        fun addNeighbor(vertex: Vertex, weight: Int) {
            neighbors.put(vertex, weight)
        }

        override fun toString(): String {
            var predecessorString = ""
            if (predecessor != null) {
                predecessorString = predecessor!!.id.toString()
            }
            return String.format(
                "Vertex[%c]: distance is %d , predecessor is '%s'",
                id,
                distance,
                predecessorString
            )
        }
    }


    private fun dijkstra(list: LinkedList<Vertex>) {
        val copys = LinkedList<Vertex>()
        copys.addAll(list)
        while (!copys.isEmpty()) {
            //每次取出一个离起始点最近的点,并将这个点在copys中删除
            val minDistanceV = extractMinDistance(copys)
            relax(minDistanceV)
        }
    }

　　//从剩余顶点中找出一个distance最小的顶点返回
    private fun extractMinDistance(list: LinkedList<Vertex>): Vertex {
        var index = 0
        for (i in 1..(list.size - 1)) {
            if (list.get(index).distance > list.get(i).distance) {
                index = i
            }
        }
        return list.removeAt(index)
    }

　　//更新某个顶点的所有邻居点的distance
    private fun relax(vertex: Vertex) {
        val map = vertex.neighbors
        for (neightbor in map.keys) {
            var neighborDistance = map.get(neightbor)
            if (neighborDistance == null) {
                neighborDistance = 0
            }
            val distance = vertex.distance + neighborDistance
            if (neightbor.distance > distance) {
                neightbor.distance = distance
                neightbor.predecessor = vertex
            }
        }
    }

    private fun getTestData(): LinkedList<Vertex> {
        val s = Vertex('s')
        val t = Vertex('t')
        val x = Vertex('x')
        val y = Vertex('y')
        val z = Vertex('z')

        s.addNeighbor(t, 10) // s->t : 10
        s.addNeighbor(y, 5) // s->y : 5
        t.addNeighbor(x, 1) // t->x : 1
        t.addNeighbor(y, 2) // t->y : 2
        x.addNeighbor(z, 4) // x->z : 4
        y.addNeighbor(t, 3) // y->t : 3
        y.addNeighbor(x, 9) // y->x : 9
        y.addNeighbor(z, 2) // y->z : 2
        z.addNeighbor(x, 6) // z->x : 6
        z.addNeighbor(s, 7) // z->s : 7

        //set start distance to 0
        s.distance = 0
        val linkedList = LinkedList<Vertex>()
        linkedList.add(s)
        linkedList.add(t)
        linkedList.add(x)
        linkedList.add(y)
        linkedList.add(z)

        return linkedList
    }

    fun doTest() {
        val list = getTestData()
        dijkstra(list)
        for (item in list) {
            println(item.toString())
        }
    }
}

运行测试：

 val testDijkstra = TestDijkstra()
 testDijkstra.doTest()

结果：

Vertex[s]: distance is 0 , predecessor is ''
Vertex[t]: distance is 8 , predecessor is 'y'
Vertex[x]: distance is 9 , predecessor is 't'
Vertex[y]: distance is 5 , predecessor is 's'
Vertex[z]: distance is 7 , predecessor is 'y'

对应下图，如果x点，他的最短路经为9：s->y->t->x

五、算法优化

我们现在是通过遍历所有剩余点来找出最小的distance；我们可以把剩余点保存在最小堆的优先队列中，直接取出首元素即可。调整最小堆时间复杂制为logn级别，如果使用Fibonacci Heap实现最小优先队列，时间复杂度为O(1)。