如果想在一张权重图中寻求某一点到其他点的最短路径，Dijkstra算法和Floyd算法是最常用的。
首先在介绍算法前，定义一下如何存储图，为了方便，我们约定 n 为点数，m为边数。
这是一种使用二维矩阵来进行存图的方式，适用于边数较多的稠密图使用。
// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
int[][] w = new int[N][N];
// 加边操作
void add(int a, int b, int c) {
w[a][b] = c;
}
这也是一种在图论中十分常见的存图方式，与数组存储单链表的实现一致（头插法）。这种存图方式又叫链式前向星存图，适用于边数较少的稀疏图使用。
Dijkstra算法适合权重非负的图，寻求单源最短路径，算法复杂度为O(n^2)。
需要的数据为领接矩阵w[N][N]，初始距离dis[N]，保存访问状态visit[N]，算法有两次循环，第一次循环寻求还未访问的节点中路径最短的节点，第二次循环则是根据第一次循环中选出的节点和邻接矩阵更新dis数组。
//初始化各参数（后面根据已知数据更新各数组这里就略过了）
int[][] w = new int[n][n];
int[] dis = new int[n];
boolean[] visit = new boolean[n];
for (int i = 0; i < n; i++) {
dis[i] = Integer.MAX_VALUE/2;
}
//选择第k个点作为起始点
dis[k] = 0;
//循环n次
for (int i = 0; i < n; i++) {
int t = -1;
//寻找还未结束访问的节点中，路径最短的节点
for (int j = 0; j < n; j++) {
if (!visit[j] && (t==-1 || dis[j]<dis[t]))
t=j;
}
visit[t] = true;
//根据找出的节点t，更新最短路径
for (int j = 0; j < n; j++) {
dis[j] = Math.min(dis[j], dis[t] + w[t][j]);
}
}
Floyd算法适合寻找多源最短路径，可以寻找任意出发点到任意终点的最短距离，支持路径权重为负数。算法为三层，遍历中间节点，遍历起点，遍历终点，执行松弛操作，算法复杂度为O(n^3)
int N = 110, M = 6010;
// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
int[][] w = new int[N][N];
int INF = 0x3f3f3f3f;
int n, k;
n = _n; k = _k;
// 初始化邻接矩阵,后面根据已知数据更新数组这里就略过了
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = w[j][i] = i == j ? 0 : INF;
}
}
// floyd 基本流程为三层循环：
// 枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作
for (int p = 1; p <= n; p++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
//如果借由中间节点使得路径更短，则更新路径距离
w[i][j] = Math.min(w[i][j], w[i][p] + w[p][j]);
}
}
}