给你 n 个点，m 条无向边，每条边都有长度 d 和花费 p，给你起点 s 终点 t，要求输出
起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
输入：输入 n , m，点的编号是 1~n,然后是 m 行，每行 4 个数 a,b,d,p，表示 a 和 b
之间有一条边，且其长度为 d，花费为 p。最后一行是两个数 s,t;起点 s，终点 t。n 和 m
为 0 时输入结束。(1
输出：一行有两个数，最短距离及其花费。
This is a typical shortest path problem. We could solve it with three methods, Dijkstra algorithm, Dellman-Ford algorithm and Shortest Path Faster Algorithm. In the following sections, pseudo codes are listed.
Dijkstra Algorithm:
1: void Dijkstra( Graph, source )
2: {
3: // Initialization
4: foreach vertex v in Graph
5: {
6: // set the distances to infinity
7: dist[v] = infinity;
8: // set each node with no previouse node
9: previous[v] = undefined;
10: }
11: // source node has no ditance to itself
12: dist[source] = 0;
13: // Q is a set that contains all the nodes in Graph
14: Q = Graph.nodes;
15: // travse
16: while( Q is not empty )
17: {
18: // pop a node from Q which has the smallest distance
19: // to the source node
20: u = vertex in Q with smallest distance in dist[];
21: // if the nearest node is infinity, there should be no
22: // more nodes coule be updated
23: if( dist[u] = infinity )
24: {
25: break;
26: }
27: // the node should not be update twice
28: remove u from Q;
29: // update all the neighbor nodes of current node
30: foreach neighbor v of u
31: {
32: // calculte a temp path, which go though current
33: // u, to v
34: alt = dist[u] + dist_between(u, v);
35: // if the temp path is shorter, update
36: if( alt < dist[v] )
37: {
38: dist[v] = alt;
39: previous[v] = u;
40: reorder v in Q
41: }
42: }
43: }
44: //
45: // dist[] holds the distance
46: // and previous[] contains the previous node
47: // in a shortest path
48: //
49: }
Bellman-Ford Algorithm：
1: void BellmanFord( Graph, source )
2: {
3: // initialize
4: foreach vertex v in Graph.vertices
5: {
6: // set the initial distance
7: if( v is source )
8: {
9: // source node is 0
10: v.distance = 0;
11: }
12: else
13: {
14: // the others are infinity
15: v.distance = infinity;
16: }
17: // no previous node in the shortest path
18: v.previous = null;
19: }
20: // relax the edges
21: for i from 1 to Graph.vertices.size-1
22: {
23: // update the distance, suppose a path goes
24: // from source and ends at u
25: foreach edge uv in Graph.edges
26: {
27: u = uv.source;
28: v = uv.destination;
29: // if the path is shorter than the previous
30: // path, update
31: if( u.distance+uv.weight < v.distance )
32: {
33: v.distance = u.distance + uv.weight;
34: v.previous = u;
35: }
36: }
37: }
38: // check the negative-weight cycles
39: // if such cycles exist, the result is worry
40: foreach edge uv in Graph.edges
41: {
42: u = uv.source;
43: v = uv.destination;
44: // negative circle
45: if( u.distance + uv.weight < v.distance )
46: {
47: print error;
48: exit;
49: }
50: }
51: return;
52: }
SPFA Algorithm:
1: void BellmanFord( Graph, source )
2: {
3: // initialize
4: foreach vertex v in Graph.vertices
5: {
6: // set the initial distance
7: if( v is source )
8: {
9: // source node is 0
10: v.distance = 0;
11: }
12: else
13: {
14: // the others are infinity
15: v.distance = infinity;
16: }
17: // no previous node in the shortest path
18: v.previous = null;
19: }
20: // relax the edges
21: for i from 1 to Graph.vertices.size-1
22: {
23: // update the distance, suppose a path goes
24: // from source and ends at u
25: foreach edge uv in Graph.edges
26: {
27: u = uv.source;
28: v = uv.destination;
29: // if the path is shorter than the previous
30: // path, update
31: if( u.distance+uv.weight < v.distance )
32: {
33: v.distance = u.distance + uv.weight;
34: v.previous = u;
35: }
36: }
37: }
38: // check the negative-weight cycles
39: // if such cycles exist, the result is worry
40: foreach edge uv in Graph.edges
41: {
42: u = uv.source;
43: v = uv.destination;
44: // negative circle
45: if( u.distance + uv.weight < v.distance )
46: {
47: print error;
48: exit;
49: }
50: }
51: return;
52: }
No comments:
Post a Comment