方法一: floyd
1.定义
(1)Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。
(2)思想: 动态规划(dp)，而求最短路径需要不断松弛(熟悉spfa算法的可能熟悉松弛)。
2.算法具体思想
(1)邻接矩阵dist储存路径，同时最终状态代表点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！而自己的长度为0.
(2)从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。
--上述试探具体方法为遍历图中每一个点(i,j双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化。
--如果发生改变，那么两点(i,j)距离就更改。
--重复上述直到最后插点试探完成。
(3)dp[x][y]的意思可以理解为x到y的最短路径, 其中第三步的状态转移方程为: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#3.方法1 floyd
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 顶点数
* @param m int 边数
* @param graph int二维数组 一维3个数据，表示顶点到另外一个顶点的边长度是多少
* @return int
*/
int N = 510, M = 5010; // 节点最大数量, 边最大数量
int INF = 0x3f3f3f3f; // 无穷大
// 邻接矩阵数组 w[x][y] = z 代表从 x节点 到 y节点 有权重为 c 的边
int[][] w = new int[N][N];
public int findShortestPath (int n, int m, int[][] graph) {
// 1.初始化邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = w[j][i] = (i == j ? 0 : INF);
}
}
// 2.存图
for (int[] edge : graph) {
int u = edge[0], v = edge[1], c = edge[2];
w[u][v] = Math.min(w[u][v], c);
}
// 3.最短路floyd算法, 三层循环
floyd(n);
return w[1][n] >= INF / 2 ? -1 : w[1][n];
}
void floyd(int n) {
//枚举中转点(p) - 枚举起点(x) - 枚举终点(y) - 松弛操作
for (int p = 1; p <= n; p++) { // 新加入图中节点
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++) {
// dp思想: 遍历图中每一个点(i,j双重循环)判断每一个点对距离是否因为加入的点
// 而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改。重复上述直到最后插点试探完成。
// w[x][p] + w[p][y] 这里p的顺序??
w[x][y] = Math.min(w[x][y], w[x][p] + w[p][y]);
}
}
}
}
}
方法二: dijkstra
1.算法思想
(1)通过Dijkstra计算图G中的最短路径(从顶点s开始计算)。
(2)引进两个集合S和U。
--S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，
--U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。
#4.方法二 dijkstra
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 顶点数
* @param m int 边数
* @param graph int二维数组 一维3个数据，表示顶点到另外一个顶点的边长度是多少
* @return int
*/
int N = 510, M = 5010; // 节点最大数量, 边最大数量
int INF = 0x3f3f3f3f; // 无穷大
// 邻接矩阵数组 w[x][y] = z 代表从 x节点 到 y节点 有权重为 c 的边
int[][] w = new int[N][N];
// dist[x] = y 代表 起点到 x 的最短距离为 y
int[] dist = new int[N];
// 记录哪些点已经被更新过
boolean[] visited = new boolean[N];
public int findShortestPath (int n, int m, int[][] graph) {
// 1.初始化邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = w[j][i] = (i == j ? 0 : INF);
}
}
// 2.存图
for (int[] edge : graph) {
int u = edge[0], v = edge[1], c = edge[2];
w[u][v] = Math.min(w[u][v], c);
}
// 3.最短路dijkstra算法
dijkstra(n);
return dist[n] >= INF / 2 ? -1 : dist[n];
}
void dijkstra(int n) {
// 1.初始化: 所有点标记为[未更新], [距离无穷大]
Arrays.fill(visited, false);
Arrays.fill(dist, INF);
// 2.只有起点的最短距离为0
dist[1] = 0;
// 3.迭代n次
for (int p = 1; p <= n; p++) {
// 3.1 每次找到 [未被更新] && [距离最小] 的节点t
int t = -1;
for (int i = 1; i <= n; i++) {
if (!visited[i] && (t == -1 || dist[i] < dist[t])) {
t = i;
}
}
// 3.2 标记为更新
visited[t] = true;
// 3.3 用t节点的[最短距离]去更新其他节点
for (int i = 1; i <= n; i++) {
dist[i] = Math.min(dist[i], dist[t] + w[t][i]);
}
}
}
}
