基于贪心算法求解单源最短路径问题

算法描述

给定带权有向图$G=(V,E)$，其中每条边的权都是非负实数。另外，还给定$V$中的一个顶点，称为源。现在要计算从源到所有其他各个顶点的最短路径长度。这里路劲的长度是指路上各边权之和。

算法设计

设置顶点集合$S$并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到d该顶点的最短路径长度已知。初始时，$S$中仅含有源，设$u$是$G$的某一个顶点，把从源到$u$且中间只经过$S$中顶点的路径成为从源到$u$的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。

图的存储采用邻接矩阵G[n][n],这里n是顶点个个数。G[i][j]（$0<=j<n，0<=i<n$）则表示第i个顶点到第j个顶点的边的权值，如果G[i][j]等于0则说明i到j没有边。

描述算法

① 将用例数据从文件中读取到数组中，初始化所有数组包括dist数组和resSet数组（访问标记）；

② 进行基于贪心算法的松弛操作如下；

③选取dist数组中尚未访问的最小值结点u，标记该结点并且以该节点为出发点，遍历该节点能够到达的所有未被访问的顶点v；

④ 若遍历到的顶点v此时的dist最短路径值大于起始结点经过u结点到达v结点的路径长度，则说明经u结点到达v结点的路径长度更优，进行松弛操作，并且将prev设置为u；

⑤重复③④步骤直到我们所要求的最终结点设置为已访问；

⑥输出结果

DIJKSTRA(G[n][n] s)
	dist[s] = ∞
	resSet[s] = true//结束顶点的集合
	for i=0 to n by i++
		dist[i]=G[s][i]
	while true{
		u = extractMin()
		if(u==-1){
			break
		}
		resSet[u] = true
		for i=1 to n by i++
			if(resSet[i] == false)
				dist[i]=max(dist[i], dist[u][i])
	}

算法正确性证明

算法复杂性分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

算法实现与测试

import java.util.Arrays;

public class App {

    public static void main(String[] args) throws Exception {
        int [][]G = {
                {0,10,Integer.MAX_VALUE,30,100},
                {Integer.MAX_VALUE,0,50,Integer.MAX_VALUE,Integer.MAX_VALUE},
                {Integer.MAX_VALUE ,Integer.MAX_VALUE ,0, Integer.MAX_VALUE,10},
                {Integer.MAX_VALUE,Integer.MAX_VALUE,20,0,60},
                {Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,0}
        };

        Dijkstra dijkstra = new Dijkstra(G, 0);
        dijkstra.process();
        System.out.println(Arrays.toString(dijkstra.dist));

    }

}
class Dijkstra{
    int []dist;
    boolean []resSet;
    int [][]G;
    int source;
    int []pre;

    void process(){
        dist = new int[G.length];
        dist[source] = Integer.MAX_VALUE;
        resSet[source] = true;
        for (int i = 0; i < dist.length; i++) {
            dist[i] = G[source][i];
            if(dist[i] != Integer.MAX_VALUE){
                pre[i] = source;
            } else {
                pre[i] = -1;
            }
        }
        while(true){
            int u = extractMin();
            if(u == -1){
                break;
            }
            resSet[u]=true;
            for (int i = 0; i < G.length; i++) {
                if(!resSet[i] && G[u][i] != Integer.MAX_VALUE){
                    int tmp = dist[u]+G[u][i];
                    if(dist[i]>tmp){
                        dist[i] = tmp;
                        pre[i]=u;
                    }
                }
            }

        }
    }

    int extractMin(){
        int min = Integer.MAX_VALUE;
        int res = -1;
        for (int i = 0; i < dist.length; i++) {
            if(!resSet[i] && dist[i] < min){
                min = dist[i];
                res = i;
            }
        }
        return res;
    }
    Dijkstra(int [][]G,int source){
        this.G = G;
        this.source = source;
        dist = new int[G.length];
        resSet = new boolean[G.length];
        pre = new int[G.length];
    }
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5dPx2Yh9-1637163020981)(/home/liuhd/.config/Typora/typora-user-images/image-20211117231838544.png)]

输出结果：

[0, 10, 50, 30, 60]

心得体会

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择

利用贪心法求解的问题应具备如下2个特征 。

1、贪心选择性质

一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解 。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析 。

择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解 。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析 。