The STUDIA UNIVERSITATIS BABEŞ-BOLYAI issue article summary

The summary of the selected article appears at the bottom of the page. In order to get back to the contents of the issue this article belongs to you have to access the link from the title. In order to see all the articles of the archive which have as author/co-author one of the authors mentioned below, you have to access the link from the author's name.

 
       
         
    STUDIA INFORMATICA - Issue no. 2 / 2002  
         
  Article:   MINIMUM COST PATH IN A HUGE GRAPH.

Authors:  ION COZAC.
 
       
         
  Abstract:  Suppose we have a weighted graph G = (V;E; c); where V is the set of vertices, E is the set of arcs, and c : E ! R+ is the cost function. Determining a minimum cost path between two given nodes of this graph can take O(mlog n) time, where n = jV j and m = jEj: If this graph is huge, say n ~ 700000 and m ~ 2000000; determining a minimum cost path can be a serious time consuming task. So we must develop an algorithm that quickly determines a path having the cost near the optimum one.  
         
     
         
         
      Back to previous page