带权图单源最短路径求解——Dijkstra算法及实现

算法思想及数据结构

Dijkstra是一种基于贪心策略的算法实现，追求局部最优进而求解全局最优。
以下的流程，所给的带权图将以邻接矩阵arcs[][]的形式存储，arcs[i][j]表示有向边的权值，若两结点间无直接的边相连，则距离表示为-1（即用-1来表示不可达）。
除举证arsc int[][]外，还需构造三个辅助数组：

• final []bool

  标记各点是否已经找到最短路径

• dust []int

  记录当前各点到源的最小距离

• path []int

  记录到达各点的最短路径的目标点的前一个点的下标，通过path[]就能够还原出最短路径

算法流程

1. 初始化dust,设源点为x，dist[]=arcs[x][],这表示与源直接连接的点的距离。

2. 遍历dist[],找到min(dist[i])，修改final[i]=true，path[i]=0(排除final[i]=true，和dist[i]=-1的值)

3. 遍历arcs[i][]，若存在dist[j]>dist[i]+arsc[i][j]（-1视为无限大），修改dist[j]=dist[i]+arsc[i][j]，path[j]=i

4. 重复二、三步，至多n-1次后算法结束。

算法复杂度

使用邻接矩阵存储的情况下，由于最坏的情况下需要遍历n遍，因此时间复杂度为 $O(|V|^2)$

代码实现

package main

import "fmt"

func dijkstra(graph [][]int, start int) ([]int, []int) {
	final := make([]bool, len(graph))
	dist := make([]int, len(graph))
	copy(dist, graph[start])
	path := make([]int, len(graph))
    for i := 0; i < len(path); i++ {
        path[i] = start
    }

	for i := 0; i < len(graph)-1; i++ {
		min := -1
		// 遍历dist，找到当前还未确定最短距离的点中距离最短的那个，将其标记为已确定最短距离
		for j := 0; j < len(graph); j++ {
			if !final[j] && dist[j] != -1 {
				if min == -1 {
					min = j
				}
				if dist[j] < dist[min] {
					min = j
				}
			}
		}
		// 说明已经没有任何一个可达的点，程序结束
		if min == -1 {
			for a := 0; a < len(graph); a++ {
				if dist[a] == -1 {
					path[a] = -1
				}
			}
			return dist, path
		}

		final[min] = true
		// 更新dist，寻找是否有更小的距离去找到可达点
		for k := 0; k < len(graph[min]); k++ {
			if graph[min][k] != -1 && (graph[min][k]+dist[min] < dist[k] || dist[k] == -1) {
				dist[k] = graph[min][k] + dist[min]
				path[k] = min
			}
		}
	}
    // 更新path的值，将不可达的点对应路径改为-1（初值为0，-1表示不可达）
	for a := 0; a < len(graph); a++ {
		if dist[a] == -1 {
			path[a] = -1
		}
	}

	return dist, path
}

func main() {
	graph := [][]int{
		{-1, 1, 2, 8},
		{-1, -1, 3, 2},
		{-1, -1, -1, 1},
		{-1, -1, -1, -1},
	}
	dist, path := dijkstra(graph, 0)
	fmt.Println("dist:", dist)
	fmt.Println("path:", path)
}

测试所用用例如下：