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". alpar@1641: /// alpar@1641: /// \include dijkstra_demo.cc athos@1583: athos@1182: #include athos@1182: athos@1182: #include athos@1182: #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: alpar@1641: std::cout << "This program is a simple demo of the LEMON Dijkstra class." alpar@1641: << std::endl; alpar@1641: std::cout << alpar@1641: "We calculate the shortest path from node s to node t in a graph." alpar@1641: << std::endl; alpar@1641: std::cout << std::endl; athos@1530: athos@1530: alpar@1641: std::cout << "The id of s is " << g.id(s)<< ", the id of t is " alpar@1641: << g.id(t) << "." << std::endl; athos@1182: athos@1583: std::cout << "Dijkstra algorithm demo..." << std::endl; athos@1182: athos@1182: Dijkstra dijkstra_test(g,len); athos@1182: athos@1182: dijkstra_test.run(s); alpar@1641: alpar@1641: std::cout << "The distance of node t from node s: " alpar@1641: << dijkstra_test.dist(t) << std::endl; athos@1182: alpar@1641: std::cout << "The shortest path from s to t goes through the following " alpar@1641: << "nodes (the first one is t, the last one is s): " alpar@1641: << std::endl; alpar@1641: alpar@1641: for (Node v=t;v != s; v=dijkstra_test.predNode(v)) { alpar@1641: std::cout << g.id(v) << "<-"; alpar@1641: } athos@1182: athos@1182: std::cout << g.id(s) << std::endl; athos@1182: athos@1182: return 0; athos@1182: }