算法-贪心算法-最短路径

算法-贪心算法-最短路径 一，问题分析

最短路径问题：给定一个有向带权图G=（V,E），再设其中一个点为源点，现在要计算从源到其他所有各个节点的最短路径长度（权重）。

二，算法设计

1.我们可以使用迪杰斯特拉算法：先求出长度最短的一条路径，参照该路径求出长度次短的路径，依次扩展节点，知道到达源节点。
2.基本思想：
假设源点为u，设定2个集合S和V-S，S集合中刚开始只有u一个顶点，当扩展节点寻找最短路径时，将其找到的最短路径相连的节点加入到S中，而从V-S集合中移除，并用dist[]数组记录每个顶点所对应的最短路径长度。当S中包含了所有节点，dist【】数组就是从源到其他顶点的最短路径长度。
3.算法步骤：
①数据结构:
map[][]:地图的带权邻接矩阵，顶点u到v存在一条边，则map[u][v]=该边权值，否则等于无穷。
dist[i]:记录源点到i顶点的最短路径长度
p[i]:记录最短路径i顶点的前驱
②初始化:
令集合S={u}，对于集合V-S中的所有顶点x,
初始化dist[i]=map[u][i]，如果源点u到顶点i有边相连，初始化p[i]=u，否则p[i]=-1。
③找最小：
在集合V-S中依照贪心策略来寻找使得dist[j]
具有最小值的顶点t，顶点t就是集合V-S中距离源点u最近的顶点。
④加入S集合：
将顶点t加入集合S中，同时更新V-S。
⑤判断是否结束:
V-S为空就结束，否则继续下一步
⑥借助中间节点：
在③中，当找到了源点u到t的最短路径，我们就以后的 *** 作都可以借助t来寻找最短路径。
如果dist[j]>dist[t] +map[t][j]，更新dist[j]=dist[t]+map[t][j]，记录顶点j的前驱为t,有
p[j]=t， 转第3步。

java代码：

package com.weikun.greedy;


public class C {
    private static int n = 5;
    private static int INF = Integer.MAX_VALUE;
    private static int dist[] = new int[n + 1];//最短路径 n+1 代表从1开始计数 0号废弃
    private static int p[] = new int[n + 1];   //前驱节点  n+1 代表从1开始计数 0号废弃
    //如果flag[i]等于true，说明顶点i已经加入到集合S中，；否则顶点i输入集合V-S
    private static boolean flag[] = new boolean[n + 1];  //n+1 代表从1开始计数 0号废弃

    private static void dijkstra(int u, int map[][]) {
        for (int i = 1; i <= n; i++) {//1次循环
            dist[i] = map[u][i];//初始化源点u到其他各个顶点的最短路径长度。
            flag[i] = false;
            //如果源点1到顶点i有边相连，初始化前驱(前一节点)数组p[i]=l，否则p[i]=-1，
            if (dist[i] == INF) {
                p[i] = -1;//源点u到该顶点的路径长度为无穷大 说明顶点i与源点u不相邻
            } else {
                p[i] = u;//说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u
            }
        }
        dist[u] = 0;//1 到 1没有距离
        flag[u] = true;//初始时 集合S中只有一个元素 ：源点u
        for (int i = 1; i <= n; i++) {//2次循环
            int temp = INF, t = u;//找V-S集合中dist[]最小的顶点t
            for (int j = 1; j <= n; j++) {//在集合V-S中寻找距离源点u最近的顶点t 3次循环
                if (!flag[j] && dist[j] < temp) {//!flag[j] 没有访问
                    t = j;//找到了最短距离的顶点
                    temp = dist[j];//继续寻找
                }
            }
            if (t == u) {
                return;//找不到最短距离的顶点t了，跳出循环
            }
            flag[t] = true;//否则，退出循环 ，此时t就是最短距离的顶点将t加入集合 设置已经访问了t顶点
            for (int j = 1; j <= n; j++) {//更新集合V-S中与t邻接的顶点到源点u的距离 4次循环#
                if (!flag[j] && map[t][j] < INF) {//!s[j]表示j在V-S中
                    if (dist[j] > (dist[t] + map[t][j])) {//
                        dist[j] = dist[t] + map[t][j];//更新 最短距离 将更小放入最短距离集合
                        p[j] = t;//t是其最短距离的前驱节点 放入p中
                    }
                }

            }

        }
    }

    public static void main(String[] args) {
        int map[][] = {
                //0    1    2    3    4    5
                {INF, INF, INF, INF, INF, INF},//0
                {INF, INF, 2, 5, INF, INF},//1
                {INF, INF, INF, 2, 6, INF},//2
                {INF, INF, INF, INF, 7, 1},//3
                {INF, INF, INF, 2, INF, 4},//4
                {INF, INF, INF, INF, INF, INF},//5
        };
        dijkstra(1, map);
        System.out.println("小明所在的位置："+1);
        for (int i = 1; i <= n; i++) {
            System.out.printf("小明【1】要去【%d】位置：" ,i);
            if (dist[i] == INF) {
                System.out.println("抱歉，无路可达");
            } else {
                System.out.println("最短距离为" + dist[i]);
            }
        }
    }


}

c++代码:

#include
using namespace std;
int MAXN=1e8+5;
const int n=5;
int dist[n+1];
int p[n+1]；
bool flag[n+1];

void dijkstra(int u,int maps[][]){
    //初始化
    for(int i=1;i<=n;i++){
        dist[i]=maps[u][i];
        flag[i]=false;//不在S集合中
        if(dist[i] == MAXN){
            p[i]=-1;
        }
        else{
            p[i]=u;
        }
    }
    dist[u]=0;
    flag[u]=true;//加入到S集合中
    for(int i=1;i<=n;i++){
        int temp=MAXN,t=u;
        for(int j=1;j<=n;j++){//寻找V-S集合中距离u最近的顶点t
                if(flag[j]==false && dist[j] (dist[t]+maps[t][j])){
                    dist[j]=dist[t]+maps[t][j];
                    p[j]=t;
                }
            }
        }
        
    }
}
int main()
{
    
}