最短路径问题最经典的算法就是Dijkstra算法，虽然不如Floyd算法能够求全源的最短路径，但是在效率上明显强于Floyd算法。

想了解Floyd算法的读者可以参考动态规划在求解全源最短路径中的应用（JAVA）--Floyd算法

单源最短路径问题是对于加权连通图来说，我们给定一个起点，求出它到其他顶点之间的一系列最短路径。这个问题不同于从一个起点出发访问其他所有顶点的问题（TSP问题），这种问题所求的一组路径都是从起点出发通向图中的一个不同顶点。这些路径中可能存在公共边。

Dijkstra算法和Prim算法的用法比较相似，二者都是从顶点集中选择一个顶点来构造树，但是解决的问题是不同的。Dijkstra算法每次比较的是路径的总长度，每次要把权重相加。而Prim算法则直接比较权重。

以下图的例子来描述Dijkstra算法的过程：

Input:

5 7
1 2 3
1 4 7
2 4 2
2 3 4
3 4 5
3 5 6
4 5 4

Output:

0 3 7 5 9 

完整代码如下：

import java.util.Scanner;

public class Main {
    static int[][] e = new int[10][10];
    static int[] book = new int[10];
    static int[] dis = new int[10];
    static int n, m;
    static int min = 99999999;
    static int mark = 0;
    static Scanner input = new Scanner(System.in);

    public static void main(String[] args) {
        n = input.nextInt();
        m = input.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    e[i][j] = 0;
                } else {
                    e[i][j] = 99999999;
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            int a = input.nextInt();
            int b = input.nextInt();
            int c = input.nextInt();
            e[a][b] = c;
            e[b][a] = c;
        }
        /**
         * 1到其他各点的距离
         * */
        for (int i = 1; i <= n; i++) {
            dis[i] = e[1][i];
        }
        book[1] = 1;

        dijkstra();

        for (int i = 1; i <= n; i++) {
            System.out.print(dis[i] + " ");
        }
    }
    public static void dijkstra() {
        /**
         * 遍历n-1次，每次找出一个 1到某个点的最短距离
         * */
        for (int i = 1; i <= n-1; i++) {
            min = 99999999;
            /**
             * 选出离1号点最近的顶点
             * */
            for (int j = 1; j <= n; j++) {
                if (book[j] == 0 && dis[j] < min) {
                    min = dis[j];
                    mark = j;
                }
            }
            book[mark] = 1;
            /**
             * 松弛
             * */
            for (int j = 1; j <= n; j++) {
                if (e[mark][j] < 99999999) {
                    if (dis[j] > dis[mark] + e[mark][j]) {
                        dis[j] = dis[mark] + e[mark][j];
                    }
                }
            }
        }
    }
}

时间复杂度：O(nlogn)，当然如果能够采用邻接表存储数据会更快。