Dijkstra算法的 java 实现

求无权最短路径，使用广度优先搜索即可。如果是有权图，就要用Dijkstra算法。Dijkstra算法是一种贪婪算法。读者可以结合输出和注释尝试理解。

---

代码

import java.util.Arrays;

public class Test {
//无限大
static int INF = Integer.MAX_VALUE;

//dis保存某点到各点的花费，不可到为INF
static int [] [] dis = new int [6][6]; 

//MINDIS是最终经Dijkstra算法之后算出从0点到各点最短路径
static int [] MINDIS = new int [6];

//marked为1，表示已经标定
static int [] marked = new int [6];

static void Dijkstra() {
        MINDIS[0] = 0;
        marked[0] = 1;

//6次循环，每次标定一个点
for(int i = 0; i < 6; i++) {
int min = 0;
int minDis = INF;

//寻找花费最少的路径并标定
for(int j = 1; j < 6; j++) {
if(marked[j] == 0 && MINDIS[j] < minDis) {
                    min = j;    
                    minDis = MINDIS[j];
                }
            }

            marked[min] = 1;
            System.out.println("标定 " + min + " :");

//略过标定的点，因为已经花费最少。如果已保存的最小花费比从 min 点的花费要大，就更新最小花费
for(int j = 1; j < 6; j++) 
if(marked[j] == 0 && MINDIS[min] != INF && dis[min][j] != INF && MINDIS[j] > dis[min][j] + MINDIS[min]) 
                    MINDIS[j] = dis[min][j] + MINDIS[min];

//输出已保存的最小花费
            System.out.println(Arrays.toString(MINDIS));
        }
    }

public static void main(String [] args) {
//初始化dis
for(int i = 0; i < 6; i++) 
for ( int j = 0; j < 6; j++)
                dis[i][j] = INF;

        dis[0][1] = 6; dis[0][2] = 3; dis[1][2] = 2; dis[1][3] = 5; dis[2][3] = 3;
        dis[2][4] = 4; dis[3][4] = 2; dis[3][5] = 3; dis[4][5] = 5;

for(int i = 0; i < 6; i++) 
for ( int j = 5; j >= i; j--)
                dis[j][i] = dis[i][j];

//初始化minDis和marked
for(int i = 0; i < 6; i++)
            MINDIS[i] = INF;

        Dijkstra();
    }
}

输出

标定 0 :
[0, 6, 3, 2147483647, 2147483647, 2147483647]
标定 2 :
[0, 5, 3, 6, 7, 2147483647]
标定 1 :
[0, 5, 3, 6, 7, 2147483647]
标定 3 :
[0, 5, 3, 6, 7, 9]
标定 4 :
[0, 5, 3, 6, 7, 9]
标定 5 :
[0, 5, 3, 6, 7, 9]