I gang

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

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.

Færdigheder: C++ Programmering

Se mere: template stl, stl template, stl standard template library, stl standard, stl programming, stl cplusplus, stl c, std template library, std template, standard template library stl, standard stl, n2, flux application, dikjstra, template library, c stl, std library, programming structures, programming standard library, library standard, carte programming, stl library, standard template library, programming tests, elle b

Om arbejdsgiveren:
( 1 bedømmelse ) Montr?al, Canada

Projekt-ID: #4053634

Tildelt til:

vuquangvinh0412

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

$30 CAD på 1 dag
(2 bedømmelser)
1.6

5 freelancere byder i gennemsnit $118 for dette job

it2051229

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

$30 CAD in 0 dage
(60 bedømmelser)
5.0
nani01029x

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

$180 CAD på 1 dag
(21 bedømmelser)
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 dage
(4 bedømmelser)
2.7
geniousPHP

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

$149 CAD på 1 dag
(0 bedømmelser)
0.0