# Differences

This shows you the differences between two versions of the page.

 en:projects:details:fred02 [2009/06/05 10:17]didier en:projects:details:fred02 [2010/01/20 13:08]masoud Both sides previous revision Previous revision 2010/01/20 13:08 masoud 2010/01/20 13:08 masoud completed2009/09/18 13:53 cronie 2009/09/18 13:52 cronie 2009/06/05 23:12 cangiani 2009/06/05 10:17 didier 2009/04/07 15:21 admin created Next revision Previous revision 2010/01/20 13:08 masoud 2010/01/20 13:08 masoud completed2009/09/18 13:53 cronie 2009/09/18 13:52 cronie 2009/06/05 23:12 cangiani 2009/06/05 10:17 didier 2009/04/07 15:21 admin created Line 1: Line 1: - === Shortest paths in a Euclidean graph === - - Finding the shortest path between two vertices in a weighted graph is a fundamental problem with numerous applications. There are of course classical algorithms for this problem like Dijkstra'​s Algorithm, but in many applications this algorithm is too slow, for example when we want to compute the best path between two cities in the graph of the roads of a whole country. - - For this kind of problem, it is crucial to use the Euclidean property of the graph to design better algorithms. A classical approach is to use the A* search which uses an estimation on the minimal distance to minimize the search space in Dijkstra'​s algorithm. But if one is allowed to do some precomputations on the graph and to store some extra data, it is possible to answer any shortest path query between two points very efficiently. - - The aim of the project is to understand and implements some of these algorithms. ​ - - --- - ---- dataentry project ---- ---- dataentry project ---- title : Shortest paths in a Euclidean graph title : Shortest paths in a Euclidean graph - contactname: ​Frederic Didier + contactname: ​Harm Cronie - contactmail_mail: ​frederic.didier@epfl.ch + contactmail_mail: ​harm.cronie@epfl.ch - contacttel: 021 6931204 + contacttel: 021 6936793 - contactroom:​ BC 128 + contactroom:​ BC 150 type : bachelor semester type : bachelor semester - status : available + status : completed table : projects table : projects created_dt : 2009-01-01 created_dt : 2009-01-01 - taken_dt : + taken_dt : 2009-06-15 - completed_dt : + completed_dt : 2010-01-13 - by : + by : Auguste Carmen Lunang Pomkam output_media : output_media : ====== ====== template:​datatemplates:​project template:​datatemplates:​project ---- ---- + + Finding the shortest path between two vertices in a weighted graph is a fundamental problem with numerous applications. There are of course classical algorithms for this problem like Dijkstra'​s Algorithm, but in many applications this algorithm is too slow, for example when we want to compute the best path between two cities in the graph of the roads of a whole country. + + For this kind of problem, it is crucial to use the Euclidean property of the graph to design better algorithms. A classical approach is to use the A* search which uses an estimation on the minimal distance to minimize the search space in Dijkstra'​s algorithm. But if one is allowed to do some precomputations on the graph and to store some extra data, it is possible to answer any shortest path query between two points very efficiently. + + The aim of the project is to understand and implements some of these algorithms. ​