leetcode_1368（使网格图至少有一条有效路径的最小代价)

原题链接

最短路径

解决问题：

单点最短路径：给定一副加权有向图和一个起点S，回答“从S到V是否存在一条有向路径？如果有，请找出总权值最小的那条路径。”等类似问题。

最短路径的性质：

• 路径是有向的
• 权重不一定等价于距离（权重还可以是时间，花费等一系列代价）
• 负权重会使问题更加复杂
• 最短路径一般都是简单的（我们的算法会忽略构成环的零权重边）
• 最短路径不一定是唯一的

  最短路径树：

  定义：给定一副加权有向图和一个顶点S，以S为起点的一颗最短路径树是图的一副子图，他包含S和从S可达的所有顶点。这颗有向树的根节点为S，树的每条路径都为最短路径。

  Dijkstra算法

  Dijkstra 算法是求取单源最短路径的常用算法，其基本思想是每次用当前未拓展且具有最小权值的点来更新源点到其余顶点的距离。
  迪杰斯特拉算法的成功率是最高的，但是搜索速度是最慢的，求一个点到其它所有点的最短路径的时间复杂度为是O(n)。

  BFS（解决起来比较简单）

  主要思路是，
  1.创建一个二位数组graph来存放已知的到每个节点的最短路径，step二维数组为四种方向，队列queue来存放需要观察的点
  2.将（0，0）点放入队列中，开始循环直到队列为空
  3.每一个点朝四个方向都走一遍，若该值小于该点已知的最短路径则将其替换，并将该点放入队列中
  4.返回所需要点的最短路径

源代码如下：

class point{
    int x;
    int y;
    public point(int x,int y) {
        // TODO Auto-generated constructor stub
        this.x = x;
        this.y = y;
    }
}
class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] step = {{0,0},{0,1},{0,-1},{1,0},{-1,0}};
        int[][] graph = new int[m][n];
        for(int i = 0;i<m;i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.MAX_VALUE;
            }
        }
        graph[0][0] = 0;
        Queue<point> queue = new LinkedList<point>();
        queue.offer(new point(0, 0));
        while (queue.size()!=0) {
            point temPoint = queue.poll();
            for (int i = 1; i < 5; i++) {
                int xx = temPoint.x+step[i][0];
                int yy = temPoint.y+step[i][1];
                int value = graph[temPoint.x][temPoint.y]+(i==grid[temPoint.x][temPoint.y]?0:1);
                if (xx<0||yy<0||xx>=m||yy>=n) {
                    continue;
                }
                if (value<graph[xx][yy]) {
                    graph[xx][yy] = value;
                    queue.offer(new point(xx, yy));
                }
            }
        }
        return graph[m-1][n-1];
    }
}