athos@1583: /* -*- C++ -*- ladanyi@1636: * demo/dijkstra_demo.cc - Part of LEMON, a generic C++ optimization library athos@1583: * athos@1583: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport athos@1583: * (Egervary Research Group on Combinatorial Optimization, EGRES). athos@1583: * athos@1583: * Permission to use, modify and distribute this software is granted athos@1583: * provided that this copyright notice appears in all copies. For athos@1583: * precise terms see the accompanying LICENSE file. athos@1583: * athos@1583: * This software is provided "AS IS" with no warranty of any kind, athos@1583: * express or implied, and with no claim as to its suitability for any athos@1583: * purpose. athos@1583: * athos@1583: */ athos@1583: athos@1583: ///\ingroup demos athos@1583: ///\file athos@1583: ///\brief Demonstrating LEMON implementation of the Dijkstra algorithm athos@1583: /// athos@1583: /// Dijkstra's algorithm computes shortest paths between two nodes in athos@1583: /// a graph with edge lengths. Here we only show some of the athos@1583: /// facilities supplied by our implementation: for the detailed athos@1583: /// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this". athos@1583: athos@1182: #include athos@1182: athos@1182: #include athos@1182: #include athos@1526: //#include athos@1182: athos@1182: using namespace lemon; athos@1182: athos@1182: athos@1182: int main (int, char*[]) athos@1182: { athos@1182: athos@1182: typedef ListGraph Graph; athos@1182: typedef Graph::Node Node; athos@1182: typedef Graph::Edge Edge; athos@1182: typedef Graph::EdgeMap LengthMap; athos@1182: athos@1182: Graph g; athos@1182: athos@1182: //An example from Ahuja's book athos@1182: athos@1182: Node s=g.addNode(); athos@1182: Node v2=g.addNode(); athos@1182: Node v3=g.addNode(); athos@1182: Node v4=g.addNode(); athos@1182: Node v5=g.addNode(); athos@1182: Node t=g.addNode(); athos@1182: athos@1182: Edge s_v2=g.addEdge(s, v2); athos@1182: Edge s_v3=g.addEdge(s, v3); athos@1182: Edge v2_v4=g.addEdge(v2, v4); athos@1182: Edge v2_v5=g.addEdge(v2, v5); athos@1182: Edge v3_v5=g.addEdge(v3, v5); athos@1182: Edge v4_t=g.addEdge(v4, t); athos@1182: Edge v5_t=g.addEdge(v5, t); athos@1182: athos@1182: LengthMap len(g); athos@1182: athos@1182: len.set(s_v2, 10); athos@1182: len.set(s_v3, 10); athos@1182: len.set(v2_v4, 5); athos@1182: len.set(v2_v5, 8); athos@1182: len.set(v3_v5, 5); athos@1182: len.set(v4_t, 8); athos@1182: len.set(v5_t, 8); athos@1182: athos@1530: std::cout << "This program is a simple demo of the LEMON Dijkstra class."< dijkstra_test(g,len); athos@1182: athos@1182: dijkstra_test.run(s); athos@1182: athos@1182: athos@1182: std::cout << "The distance of node t from node s: " << dijkstra_test.dist(t)<