C++ Application de l'algorithme de Dikjstra sur un graphe

Completed Posted Dec 18, 2012 Paid on delivery
Completed Paid on delivery

1. Objectifs

Utiliser une bibliothèque normalisée (la «STL»).

Implémenter une représentation de graphe.

Implémenter un algorithme de recherche de chemin dans un graphe.

2. Introduction

Vous devez écrire un programme C++ nommé tp3 qui calcule des chemins de distance minimale entre des lieux dans une carte.

Votre programme doit pouvoir être lancé en ligne de commande avec la syntaxe suivante :

./tp3 [nomfichier]

où nomfichier est optionnel.

Si nomfichier est spécifié, alors votre programme doit lire dans nomfichier au moyen d'un flux de lecture C++ std::ifstream. Sinon, votre programme doit lire dans l'entrée standard (stdin) au moyen du flux d'entrée C++ std::cin. Les chemins calculés doivent être écrit dans la sortie standard (stdout) à l'aide du flux de sortie C++ std::cout.

Un squelette de départ est disponible dans tp3.zip.

3. Formats d'entrée et de sortie

3.1 Entrée

L'entrée est constituée de :

Une liste* de lieux. Un lieu est spécifié par un nom et par une coordonnée de la forme (x,y) où x et y sont des réels.

Trois tirets (---) de séparation.

Une liste* de routes. Une route est spécifiée par une paire de lieux séparés par «->» (sens unique) ou par «» (deux directions). À noter que la direction «>, il y a au moins un espace blanc (espace, tabulation ou retour de ligne) après chaque nom de lieu.

Voici un exemple d'entrée ([url removed, login to view]) :

a (5.0,40.0)

b (45.0,10.0)

c (60.0,40.0)

d (100.0,25.0)

e (100.0,62.0)

f (120.0,40.0)

---

a -> b

b -> c

c -> a

c d

c e

d f

e f

---

a f

f b

Et la carte correspondante :

3.2 Hypothèses

On suppose que les routes sont droites. Ainsi, la longueur d'une route est la distance euclidienne séparant les deux lieux qu'elle relit. Par exemple, la longueur de la route l0->l1 est de 50 unités.

Dans les tests, le nombre de requêtes sera inférieur au carré du nombre de lieux (n2). Cela devrait vous donner un indice quant à l'algorithme à utiliser (ou à ne pas utiliser).

Il peut y avoir plusieurs requêtes à partir d'un même lieu d'origine. Dans ce cas, ces requêtes peuvent être consécutives.

3.3 Sortie

Votre programme doit écrire en sortie les chemins calculés. Un chemin est spécifié par la liste des lieux à emprunter, séparés par un espace, et dans l'ordre du parcours, pour de se rendre de l'origine à la destination. S'il n'existe pas de chemin entre l'origine et la destination, il faut afficher "!" (voir [url removed, login to view]). Chaque chemin est suivi d'un saut de ligne (\n).

Voici un exemple de sortie ([url removed, login to view]) :

a b c d f

f d c a b

4. Contraintes

4.1 Librairies permises

Utiliser, autant que possible, les conteneurs de la librairie standard de C++ (Standard Template Library). Cette contrainte vise à mettre en pratique l'utilisation d'une bibliothèque normalisée. Évidemment, vous pouvez créer vos propres structures si cela s'avère nécessaire. Cela est nécessaire lors qu'une structurée requise n'est pas offert par la STL, ou lorsque la structure offerte dans la STL ne conviennent pas à vos besoins précis. Par exemple, vous devrez fort probablement créer une classe Graphe ou Carte.

Des tests sont disponibles dans tp3-tests.zip. Les résultats attendus sont disponibles pour les 10 premiers tests.

Project Description:
1. Objectives

Use a standard library (the "STL").
Implement a graph representation.
Implement an algorithm for path finding in a graph.
2. Introduction

You need to write a C + + program that calculates named tp3 minimum distance paths between locations on a map.

Your program must be launched from the command line with the following syntax:
./tp3 [filename]
where filename is optional.
If filename is specified, then your program should read in filename using a flow reading C + + std :: ifstream. Otherwise, your program should read from standard input (stdin) with the input stream C + + std :: cin. Computed paths must be written to the standard output (stdout) using the output stream C + + std :: cout.

A skeleton is available starting in tp3.zip.

3. Input formats and output

3.1 Input

The entry consists of:

* A list of locations. A location is specified by a name and by a coordinate of the form (x, y) where x and y are real numbers.
Three dashes (---) separation.
* A list of roads. A road is specified by a pair of locations separated by "->" (one-way) or "" (both directions). Note that the direction "> there is at least one white space (space, tab or newline) after each place name.

Here is an example entry (test0.txt)

a (5.0,40.0)
b (45.0,10.0)
c (60.0,40.0)
d (100.0,25.0)
e (100.0,62.0)
f (120.0,40.0)
---
a -> b
b -> c
c -> a
c d
c e
dpf
f e
---
a f
f b
And the corresponding map:


3.2 Assumptions

It is assumed that the roads are straight. Thus, the length of a road is the Euclidean distance between the two places she reads. For example, the length of the road-l0> l1 is 50 units.
In tests, the number of requests is less than the square of the number of places (n2). This should give you a clue as to which algorithm to use (or not use).
There may be multiple requests from the same place of origin. In this case, these queries may be consecutive.

3.3 Released

Your program must write output paths calculated. A path is specified by the list of places to borrow, separated by a space, and in the order of the route for travel from origin to destination. If there is no path between the origin and destination, must display "!" (See test2.txt). Each path is followed by a newline (\ n).

Here is an example of output (test0.txt.resultat)

a b c d f
f a b c d
4. Constraints

4.1 Libraries permitted

Use as much as possible, the containers in the standard library of C + + Standard Template Library (). This constraint aims to put into practice the use of a standard library. Obviously, you can create your own structures if necessary. This is necessary when a structured requested is not provided by the STL, or when the structure provided in the STL does not suit your needs. For example, you will likely create a class graph or Map.

Tests are available in tp3-tests.zip. The expected results are available for the first 10 tests.

C++ Programming

Project ID: #4053634

About the project

5 proposals Remote project Active Dec 18, 2012

Awarded to:

vuquangvinh0412

Let me help you! Check your PMB and reply me ASAP.

$30 CAD in 1 day
(2 Reviews)
1.6

5 freelancers are bidding on average $118 for this job

it2051229

Dijstra's algorithm? If only you can tell this in English I can do this for you.

$30 CAD in 0 days
(60 Reviews)
5.0
nani01029x

Let me help you. Please check your pm for more details.

$180 CAD in 1 day
(21 Reviews)
4.1
ceruleusX

I can help you if you can provide details on English. As I can see, you need Dijkstra Algorithm implemented in C/C++ - I have experience with that.

$200 CAD in 2 days
(4 Reviews)
2.7
geniousPHP

Salut, je peux t'aider pour programmer l'algorithme Dijkstra

$149 CAD in 1 day
(0 Reviews)
0.0