Projet Fin D'année

PLAN DU MINI PROJET

Sommaire Pages

INTRODUCTION…………………………………………………………………………………………………….2

Première partie : Phase théorique…………………………………………………………………………3

I. RESOLUTION DU PROBLEME……………………………………………………………………….4

1. Définition d’un graphe……………………………………………………………………………4

2. Détermination du plus court chemin………………………………………………………5

2.1 Principe……………………………………………………………………………………..5

2.2 Méthode de Dijsktra………………………………………………………………….6

2.2.1 Principe…………………………………………………………………………………..7

2.2.2 Algorithme………………………………………………………………………………7

3. Application : Graphe appliqué aux communes du district d’Abidjan…………8

3.1 Analyse du problème…………………………………………………………………….8

3.2 Code C ………………………………………………………………………………………….9

Deuxième partie : Phase pratique…………………………………………………………………………13

II. PRESENTATION DU LOGICIEL DE TRAVAIL……..............................................14

Exécution du code avec le compilateur DEV C++…………………………………………16

 Sorties d’écran……………………………………………………………………………………………16

CONCLUSION……………………………………………………………………………………………………....20

BIBLIOGRAPHIE…………………………………………………………………………………………………….21

INTRODUCTION

L’utilisation des graphes s’étend sur plusieurs domaines scientifiques dont l’informatique, la télécommunication, la topologie. En effet, la théorie des graphes peut également être appliquée au domaine à la géographie des transports c’est-à-dire au réseau routier d’une ville, d’une région, d’un pays et même d’un continent.

Ainsi, le problème est de savoir, comment déterminer le trajet le plus court reliant deux sommets d’un réseau routier symbolisé par un graphe?

Tel est le thème de notre Mini projet d’informatique en langage C.

Pour répondre à cette problématique, nous allons dans un premier temps définir la notion de graphe ainsi que ses différentes caractéristiques. Ensuite, nous exploiterons le procédé de Dijkstra relatif à la détermination du plus court chemin. Enfin, nous appliquerons l’analyse de Dijkstra pour la résolution d’un cas pratique à savoir la détermination du plus court trajet entre deux communes du district d’Abidjan.

I. RESOLUTION DU PROBLEME

1. Définition d’un graphe

Un graphe orienté G est une représentation symbolique d’un réseau. Il s’agit d’une abstraction de la réalité de sorte à permettre sa modélisation. En géographie des transports, la plupart des réseaux ont un fondement spatial, mais ceci n’est pas vrai pour tous les réseaux de transport. Toutefois, la majorité des réseaux de transport peuvent être représentés par le biais de la théorie des graphes.

En effet, un réseau de transport, comme tout réseau, peut être représenté sous forme de graphe. Ainsi, un graphe G=(S, A) consiste en ensemble de sommets S, et d’arcs A.

Dans la configuration des graphes, les sommets sont représentés par des cercles et les arcs par des flèches indiquant la distance entre deux ou plusieurs sommets. Ainsi, si (u, v) est un arc du graphe G, on dit que (u, v) part du sommet u et arrive au sommet v.

De plus si (u, v) est une arrête du graphe G, on dit que (u, v) est incidente aux sommets u et v. On rappelle qu’une arrête est une paire de sommets.

La figure ci-dessous est un exemple de Graphe

Ce graphe se définit de façon suivante = (S, A):

S = (1, 2, 3, 4, 5)

A = (1,2), (1,3), (2,2), (2,5), (4,2), (4,3), (4,5)

2. Détermination du plus chemin le plus court

Qui dit trajet dit problème de plus courts chemins.

En réalité, la détermination du plus court chemin découle de la problématique suivante :

Etant donné un réseau défini par un ensemble de nœuds (sommets) et un ensemble de liaisons (arcs) entre ces nœuds caractérisés par un certain poids (distances), comment trouver le chemin (trajet) le plus

...