Saturday, June 16, 2012

最短路径算法

问题描述:
给你 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