Shortest Path Algorithm：Dijkstra

发表于   |   分类于   |  

Background

Tony, a clever boy, whose dream is travelling around world, has no sense of direction.The summer vacation is coming and Tony decides to see the world outside.But his the length of the vacation is limited, while he has a lot of homework needs to be done.So Tony wants to find a nearest place that he wants to visit.Sadly, there is no railway station in his hometown and he needs to arrive in other town adjoining first.

Input && Output

Input
There is three integer in the first line:
the first integer T represents the number of path;
the second integer S represents the number of town adjoining to Tony’s hometown;
the third integer D represents the number of the place which Tony want to visit.

Then there are T lines datum and each line has three integer:
the first integer and the second represent the identity of two places;
the third integer represents the time which Tony need to travel between the two places.

The T+2 line has S integer which represent the identity of the towns adjoining to Tony’s hometown.

The T+3 line has D integer which represent the place where Tony wants to go.

Output
The shortest time Tony will to spend to arrive any place he wants to visit.

Sample

Input
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10

Output
9

Dijkstra

We need：

  1. an array Dj to store the shortest path weight to every node;
  2. an array vis to mark the node we have expanded;
  3. an array of two dimensions to store the weight of each path.

Attentions:

  1. each array needs to be initialized;
  2. there maybe two paths of different weight between two adjoined places;
  3. the weight b to a is the same as a to b;
  4. we create an super source and the weight between super source and the node can be source is 0.

Core：
Dj[x] = min{Dj[x], Dj[inx]+m[inx][x]}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Title：Dijkstra AC code
// Author： Call偶围城
#include <stdio.h>
#define MAX 1000
#define INF 1000000
int T, S, D;
int total;
int Dj[MAX+1];
int vis[MAX+1];
int m[MAX+1][MAX+1];
void Dijkstra() {
	int i, j, k;
	int inx;
	int min;
	for (i = 1;i < total;i++) {
		min = MAX;
		for (j = 1;j <= total;j++) {
			if (vis[j] == 0 && Dj[j] < min) {
				inx = j;
				min = Dj[j];
			}
		}
		vis[inx] = 1;
		for (j = 1;j <= total;j++) {
			if (vis[j] == 0 && Dj[inx]+m[inx][j] < Dj[j])
				Dj[j] = Dj[inx] + m[inx][j];
		}
	}
}
int main() {
	int i, j, k;
	int a, b, t;
	int shortest;
	while (scanf("%d%d%d", &T, &S, &D) != EOF) {
		for (i = 0;i <= MAX;i++)
			for (j = 0;j <= MAX;j++)
				m[i][j] = INF;
		total = 1;
		for (i = 1;i <= T;i++) {
			scanf ("%d%d%d", &a, &b, &t);
			if (a > total) total = a;
			if (b > total) total = b;
			if (m[a][b] > t)
				m[a][b] = m[b][a] = t;
		}
		for (i = 0;i <= MAX;i++) {
			vis[i] = 0;
			Dj[i] = MAX;
		}
		vis[0] = 1;
		m[0][0] = 0;
		for (i = 0;i < S;i++) {
			scanf("%d", &k);
			m[0][k] = m[k][0] = 0;
			Dj[k] = 0;
		}
		
		Dijkstra();
		shortest = INF;
		for (i = 0;i < D;i++) {
			scanf("%d", &k);
			if (shortest > Dj[k])
				shortest = Dj[k];
		}
		printf("%d\n", shortest);
	}
	return 0;
}