1 | #include <iostream> |
---|

2 | |
---|

3 | #include <lemon/list_graph.h> |
---|

4 | #include <lemon/dijkstra.h> |
---|

5 | //#include <lemon/bits/item_writer.h> |
---|

6 | |
---|

7 | using namespace lemon; |
---|

8 | |
---|

9 | |
---|

10 | int main (int, char*[]) |
---|

11 | { |
---|

12 | |
---|

13 | typedef ListGraph Graph; |
---|

14 | typedef Graph::Node Node; |
---|

15 | typedef Graph::Edge Edge; |
---|

16 | typedef Graph::EdgeMap<int> LengthMap; |
---|

17 | |
---|

18 | Graph g; |
---|

19 | |
---|

20 | //An example from Ahuja's book |
---|

21 | |
---|

22 | Node s=g.addNode(); |
---|

23 | Node v2=g.addNode(); |
---|

24 | Node v3=g.addNode(); |
---|

25 | Node v4=g.addNode(); |
---|

26 | Node v5=g.addNode(); |
---|

27 | Node t=g.addNode(); |
---|

28 | |
---|

29 | Edge s_v2=g.addEdge(s, v2); |
---|

30 | Edge s_v3=g.addEdge(s, v3); |
---|

31 | Edge v2_v4=g.addEdge(v2, v4); |
---|

32 | Edge v2_v5=g.addEdge(v2, v5); |
---|

33 | Edge v3_v5=g.addEdge(v3, v5); |
---|

34 | Edge v4_t=g.addEdge(v4, t); |
---|

35 | Edge v5_t=g.addEdge(v5, t); |
---|

36 | |
---|

37 | LengthMap len(g); |
---|

38 | |
---|

39 | len.set(s_v2, 10); |
---|

40 | len.set(s_v3, 10); |
---|

41 | len.set(v2_v4, 5); |
---|

42 | len.set(v2_v5, 8); |
---|

43 | len.set(v3_v5, 5); |
---|

44 | len.set(v4_t, 8); |
---|

45 | len.set(v5_t, 8); |
---|

46 | |
---|

47 | std::cout << "The id of s is " << g.id(s)<< ", the id of t is " << g.id(t)<<"."<<std::endl; |
---|

48 | |
---|

49 | std::cout << "Dijkstra algorithm test..." << std::endl; |
---|

50 | |
---|

51 | // GraphWriter<ListGraph> writer(std::cout, g); |
---|

52 | // writer.writeEdgeMap("capacity", length); |
---|

53 | // writer.writeNode("source", s); |
---|

54 | // writer.writeNode("target", t); |
---|

55 | // writer.run(); |
---|

56 | |
---|

57 | Dijkstra<Graph, LengthMap> dijkstra_test(g,len); |
---|

58 | |
---|

59 | dijkstra_test.run(s); |
---|

60 | |
---|

61 | |
---|

62 | std::cout << "The distance of node t from node s: " << dijkstra_test.dist(t)<<std::endl; |
---|

63 | |
---|

64 | std::cout << "The shortest path from s to t goes through the following nodes (the first one is t, the last one is s): "<<std::endl; |
---|

65 | |
---|

66 | for (Node v=t;v != s; v=dijkstra_test.predNode(v)){ |
---|

67 | std::cout << g.id(v) << "<-"; |
---|

68 | } |
---|

69 | std::cout << g.id(s) << std::endl; |
---|

70 | |
---|

71 | |
---|

72 | return 0; |
---|

73 | } |
---|

74 | |
---|

75 | |
---|

76 | |
---|

77 | |
---|

78 | |
---|

79 | |
---|

80 | |
---|

81 | |
---|

82 | |
---|