数据结构与算法之图搜索最短路径（贪心算法）

1.场景：

　　1.1.对于最短路径，我们通常考虑使用贪心算法，动态规划，或者dfs，但是dfs存在的问题是随着节点数量的增加，算法时间复杂度太高，所以，对于节点数过多的图中，最短路径的计算，我们考虑使用贪心算法和动态规划，下面是给出的问题：求出1到6最短的路径，

2.代码实现：

djstl.java

package com.hfm.util;

import java.util.Arrays;

public class djstl {

    public static void main(String[] args) {
        int i = 7,j = i;
        int map[][] = new int[i][j];
        initMap(map,i,j);
        int dest[] = new int[i];
        for (int k = 0; k < dest.length; k++) {
            dest[k] = Integer.MAX_VALUE;
        }
        System.out.println(Arrays.toString(dest));
        search(dest,map,i,j);
        int loc = 0;
        for (int ds :
                dest) {
            System.out.println("点1到点"+loc+"距离："+ds);
            loc ++;
        }
    }

    public static void initMap(int map[][],int i,int j){
        for (int k = 0; k < i; k++) {
            for (int l = 0; l <j ; l++) {
                if(k == l)
                    map[k][l] = 0;
                else
                    map[k][l] = Integer.MIN_VALUE;
            }
        }
        map[1][3] = 10;
        map[1][5] = 30;
        map[1][6] = 100;
        map[2][3] = 5;
        map[3][4] = 50;
        map[4][5] = 20;
        map[4][6] = 10;
        map[5][6] = 60;
    }

    public static void search(int dest[],int map[][],int i,int j){
        int cur = 1;
        boolean mark[] = new boolean[dest.length];
        boolean visited = false;
        while (cur <dest.length){
            int min = Integer.MAX_VALUE,loc=1;
            for (int k = 0; k < dest.length; k++) {
                if(dest[k]<min && !mark[k]){
                    loc = k;
                    min = dest[k];
                }
            }
            for (int l = 1; l <j ; l++) {
                if(loc == 1 && map[loc][l] != Integer.MIN_VALUE && !visited){
                    dest[l] = map[loc][l];
                    visited = true;
                }else if(l != loc && map[loc][l] != Integer.MIN_VALUE && dest[loc] + map[loc][l]< dest[l]){
                    dest[l] = dest[loc] + map[loc][l];
                }
            }
            mark[loc] = true;
            cur ++;
        }
    }
}

 3.使用场景：

　　求最短路径，如果节点数量多，则考虑使用邻接表替换代码中的邻接矩阵