使用dijkstra算法计算最短路径数和最短路径长度

例1：1003 Emergency：

Input Specification:

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C​1​​ and C​2​​ - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c​1​​, c​2​​ and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C​1​​ to C​2​​.

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between C​1​​ and C​2​​, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

Sample Input:

5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

Sample Output:

2 4

解：

import java.util.Scanner;public class Main {private static final int MAX_required =505;private static final int MAX_int = Integer.MAX_VALUE;static int[][] map = new int[MAX_required][MAX_required];static int[] callus = new int[MAX_required];static class City{int dist;//起点城市离该城市的距离boolean visited;//有没有当过posint number;//起点城市到该城市的最短路径数int call;//起点城市离该城市的距离}static City[] city = new City[MAX_required];public static void main(String[] args) {int n,m,start,end;for (int i = 0; i < MAX_required; i++) {for (int j = 0; j < MAX_required; j++) {if(i == j) {map[i][j] = 0;continue;}map[i][j] = MAX_int;}}Scanner in = new Scanner(System.in);n = in.nextInt();m = in.nextInt();start = in.nextInt();end  = in.nextInt();for (int i = 0; i < n; i++) {callus[i] = in.nextInt();}for (int i = 0; i < m; i++) {int x = in.nextInt();int y = in.nextInt();int num = in.nextInt();map[x][y] = num;map[y][x] = num;}Dijkstra(start, end, n);}/**** @param start 开始节点* @param end 结束节点* @param n 所有节点数*/static void Dijkstra(int start, int end, int n) {for (int i = 0; i < n; i++) {city[i] = new City();city[i].dist = MAX_int;city[i].visited = false;city[i].number = 0;city[i].call = 0;}city[start].dist = 0;city[start].number = 1;city[start].call = callus[start];for (int cnt = 0; cnt < n; cnt++) {int Min = MAX_int, pos = -1;for (int i = 0; i < n; i++) {if ((city[i].visited == false) && (city[i].dist < Min)) {Min = city[i].dist;pos = i;}}if (pos == -1) {break;}city[pos].visited = true;for (int j = 0; j < n; j++) {if ((city[j].visited == false) && (map[pos][j] != MAX_int)) {if (city[j].dist > city[pos].dist + map[pos][j]) {city[j].dist = city[pos].dist + map[pos][j];city[j].number = city[pos].number;city[j].call = city[pos].call + callus[j];} else if (city[j].dist == (city[pos].dist + map[pos][j])) {city[j].number += city[pos].number;if (city[j].call < city[pos].call + callus[j]) {city[j].call = city[pos].call + callus[j];}}}}}System.out.println(city[end].number + " " + city[end].call);}
}

 

图解：

cnt为循环次数，对于连通图中的每个节点，代码都会循环一遍作为中间节点。核心思想为，根据起始节点，cnt循环的每轮确定一个当前已知最短路径的节点。直接看图：

round 1：

当前pos：A

所有pos：A

A到A的最短路径：0

	A	B	C	D	E
pos到各个节点的距离	/	1	2	1	N
如果插入pos节点，起点到各个节点的路径	0	1	2	1	N
判断后的起点到各个节点的最短路径	0	1	2	1	N

round2：

当前pos：B

所有pos：A B

A到B的最短路径：1

	A	B	C	D	E
pos到各个节点的距离	/	/	1	N	N
如果插入pos节点，起点到各个节点的路径	/	/	2	N	N
起点到各个节点的最短路径	0	1	2	1	N

 round3：

当前pos：D

所有pos：A B D

A到D的最短路径：1

	A	B	C	D	E
pos到各个节点的距离	/	/	N	/	1
如果插入pos节点，起点到各个节点的路径	/	/	N	/	2
起点到各个节点的最短路径	0	1	2	1	2

 round4：

当前pos：C

所有pos：A B D C

A到C的最短路径：2

	A	B	C	D	E
pos到各个节点的距离	/	/	/	/	1
如果插入pos节点，起点到各个节点的路径	/	/	/	/	3
起点到各个节点的最短路径	0	1	2	1	2

 

注：在计算的过程中除了路径还可以加上相同长度路径数、救援人员等参数，在第二重循环中对这些参数进行判断修改，实现最短路径数、最多救援人员等多样性的条件。