从图的一个点到另一个点到路径不止一条，每条路径的长度可能不同，把路径长度最短的那条叫做最短路径。
有权图中，应该考虑各边的权值。无权图中，可以将每条边的权值看作是1.
最短路径问题可分为两方面：
图中一个点到其余各点的最短路径图中每对点之间到最短路径 狄克斯特拉算法解决图中一点到其余各点到最短路径的问题。其基本思想位：图G=(V,E)是一个有权有向图，把顶点V分成两组，第一组为已求出最短路径的点的集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径v,…k，就将k加入到集合S中，直到全部到点都加入S集合中，算法结束)，第二组为其余未确定最短路径的点的集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入到S中。
操作步骤：
初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。重复步骤(2)和(3)，直到遍历完所有顶点。图1
如上图，以A为开头，求A到各个点的最短距离。
第一步，初始化距离，指与A直接连接的点的距离。dis[b]代表A到B点的最短距离，因而初始dis[B]=4，dis[C]=6，dis[D]=6，其余为无穷大。设置集合S用来表示已经找到的最短路径。此时，S={A}。现在得到A到各点距离**{A(0)，B(4)，C(6)，D（6），E（*），F（*），G（*）}**，其中*代表未知数也可以说是无穷大，括号里面的数值代表A点到该点的最短距离。
第2步：不考虑集合S中的点，因为dis[B]=4，是当中距离最短的，所以此时更新S，S={A,B}。接着我们看与B连接的点，分别有C，E，已经在集合S中的不看**，dis[B-C]=1，因而dis[C]=dis[B]+1=5(小于之前点dis[C],故需更新)，dis[E]=dis[B]+dis[B-E]=11**。此时**{A(0)，B(4)，C(5)，D（6），E（11），F（*），G（*）}**。
第3步：在第2步中，C点的值5最小，更新S={A，B，C}，此时看与C点直接连接的点，分别有E，F。dis[E]=dis[C]+dis[C-E]=5+6=11（和原来的值一样，不更新），dis[F]=dis[C]+dis[C-F]=5+4=9（更新）。此时**{A(0)，B(4)，C(5)，D（6），E（11），F（9），G（*）}**。
第4步：在第3步中，D点的值6最小，更新S={A，B，C，D}，此时看与D点直接连接的点，有F。dis[F]=dis[D]+dis[D-F]=6+5=11（不更新）。此时**{A(0)，B(4)，C(5)，D（6），E（11），F（9），G（*）}**。
第5步：在第4步中，F点的值9最小，更新S={A，B，C，D，F}，此时看与F点直接连接的点，有E、G。dis[E]=dis[F]+dis[F-E]=9+1=10(更新)，dis[G]=dis[F]+dis[F-G]=9+8=17(更新)。此时**{A(0)，B(4)，C(5)，D（6），E（10），F（9），G（17）}**。
第6步：在第5步中，E点的值10最小，更新S={A，B，C，D，F，E}，此时看与E点直接连接的点，只有G。dis[G]=dis[E]+dis[E-G]=10+6=16(更新)。此时**{A(0)，B(4)，C(5)，D（6），E（10），F（9），G（16）}**。
第7步：最后只剩下G值，直接进入集合S={A，B，C，D，F，E，G}，此时所有的点都已经遍历结束，得到最终结果**{A(0)，B(4)，C(5)，D（6），E（10），F（9），G（16）}**。
SUA点到个点到距离{A}{B，C，D，F，E，G}{A(0)，B(4)，C(6)，D（6），E（*），F（*），G（*）}{A，B}{C，D，F，E，G}{A(0)，B(4)，C(5)，D（6），E（11），F（*），G（*）}{A，B，C}{D，F，E，G}{A(0)，B(4)，C(5)，D（6），E（11），F（9），G（*）}{A，B，C，D}{F，E，G}{A(0)，B(4)，C(5)，D（6），E（11），F（9），G（*）}{A，B，C，D，F}{E，G}{A(0)，B(4)，C(5)，D（6），E（10），F（9），G（17）}{A，B，C，D，F，E}{G}{A(0)，B(4)，C(6)，D（6），E（10），F（9），G（16）}{A，B，C，D，F，E，G}{}{A(0)，B(4)，C(6)，D（6），E（10），F（9），G（16）} public class Dijkstra { public static int max = 99999; public static void main(String[] args) { int[][] graph = {{0, 4, 6, 6, max, max, max}, {max, 0, 1, max, 7, max, max}, {max, max, 0, max, 6, 4, max}, {max, max, 2, 0, max, 5, max}, {max, max, max, max, 0, max, 6}, {max, max, max, max, 1, 0, 8}, {max, max, max, max, max, max, max}}; int startPointIndex = 0; int[] dis = dijkastra(graph, startPointIndex); System.out.println(dis.toString()); } public static int[] dijkastra(int[][] graph, int startPointIndex) { boolean[] s = new boolean[graph.length];//集合s表示，已经求出最短路径的点的集合 for (int i = 0; i < graph.length; i++) {//初始化s集合，只有起始点 if (i == startPointIndex) { s[i] = true; } else { s[i] = false; } } int[] dis = new int[graph.length];//最短路径集合 for (int i = 0; i < graph.length; i++) {//初始化，起始点到其他点的距离。 dis[i] = graph[startPointIndex][i]; } for (int i = 0; i < graph.length; i++) {//求到每个点的最短路径 int tmpdis = max; int tmpindex = 0; for (int j = 0; j < graph.length; j++) { if (!s[j] && dis[j] < tmpdis) {//不在s集合(未求出该店的最短路径) tmpdis = dis[j]; tmpindex = j; } } //dis中距离最短的点加入到s集合中 s[tmpindex] = true; for (int j = 0; j < graph.length; j++) {//更新起点到其他点距离 if (dis[j] > dis[tmpindex] + graph[tmpindex][j]) { dis[j] = dis[tmpindex] + graph[tmpindex][j]; } } } return dis;//返回起点到每个点的最短路径长度 } }狄克斯特拉算法的时间复杂度O(n^2)。
对于第二类问题，求每对点之间的最短路径，可以通过把每个点作为源点用Dijkstra算法求最短路径。也可以用弗洛伊德(Floyd)算法。
有图G=(V,E)采用邻接矩阵cost存储，另外设置一个二维数组A用来存放当前顶点之间的最短路径长度，分量A[i][j]表示当前顶点i到顶点j到最短路径长度。Floyd算法到基本思想是递推产生一个矩阵序列A0，A1，……，Ak，……，An,其中Ak[i][j]表示从顶点i到顶点j的路径上经过的顶点编号不大于k的最短路径长度。
Floyd算法的思想可用如下的表达式来描述： A − 1 [ i ] [ j ] = c o s t [ i ] [ j ] A_{-1}[i][j]=cost[i][j] A−1[i][j]=cost[i][j]
A k + 1 [ i ] [ j ] = m i n ( A k [ i ] [ j ] , A k [ i ] [ k + 1 ] + A k [ k + 1 ] [ j ] ) ( − 1 ≤ k ≤ n − 2 ) A_{k+1}[i][j]=min(A_{k}[i][j],A_{k}[i][k+1]+A_{k}[k+1][j])(-1\leq k\leq n-2) Ak+1[i][j]=min(Ak[i][j],Ak[i][k+1]+Ak[k+1][j])(−1≤k≤n−2)
以上图为例，初始时构建最短路径长度邻接矩阵如下：
ABCDEFGA012***1614B12010**7*C*100356*D**304**E**54028F1676*209G14***890第一步，以顶点A为中介点更新矩阵。
第二步，以顶点B为中介点更新矩阵。
第三步，以顶点C为中介点更新矩阵。
第四步，以顶点D为中介点更新矩阵。
第五步，以顶点E为中介点更新矩阵。
第六步，以顶点F为中介点更新矩阵。
第七步，以顶点G为中介点更新矩阵。
public class Floyd { public static int max = 99999; public static void main(String[] args) { int[][] graph = {{0, 12, max, max, max, 16, 14}, {12, 0, 10, max, max, 7, max}, {max, 10, 0, 3, 5, 6, max}, {max, max, 3, 0, 4, max, max}, {max, max, 5, 4, 0, 2, 8}, {16, 7, 6, max, 2, 0, 9}, {14, max, max, max, 8, 9, 0}}; floyd(graph); for (int i = 0; i < graph.length; i++) { for (int j = 0; j < graph.length - 1; j++) { System.out.print(graph[i][j] + ","); } System.out.println(graph[i][graph.length - 1]); } } public static void floyd(int[][] graph) { for (int i = 0; i < graph.length; i++) {// floyd。 for (int j = 0; j < graph.length; j++) { for (int k = 0; k < graph.length; k++) { if (graph[j][i] + graph[i][k] < graph[j][k]) { graph[j][k] = graph[j][i] + graph[i][k]; } } } } } }弗洛伊德算法的时间复杂的O(n^3),n为顶点数。
POJ 1062. POJ 1125.
