Exercises 1 Minimum spanning trees and shortest paths

Lecture 10: Dijkstra’s Shortest Path Algorithm CLRS 24 3 Outline of this Lecture Recalling the BFS solution of the shortest path problem for unweighted (di)graphs The shortest path problem for weighted digraphs Dijkstra’s algorithm Given for digraphs but easily modiﬁed to work on undirected graphs 1

Exercises 1 Minimum spanning trees and shortest paths

of Dijkstra’s algorithm, all shortest paths starting at vertex r have been found The union of these paths forms a tree, which we will call the Dijkstra tree at r a Give an example of a weighted graph, whose minimum spanning tree diﬁers from all its Dijkstra trees b Prove that a minimum spanning tree and a Dijkstra tree of G always have at

Troisième partie Graphes pondérés et algorithmedeDijkstra

Correctiondel’exercice 1:Antilles2016 Des touristes sont logés dans un hôtel H Un guide souhaite faire visiter la région à ces touristes en empruntant les routes signalées comme d’intérêt touristique parl’ofﬁce dutourisme Lestronçons deroutequ’il souhaite em-prunter sont représentés sur le graphe ci-contre

Sujet et corrigé du bac en mathématiques, série ES

En utilisant l’algorithme de Dijkstra, déterminons le trajet le moins cher pour aller de A à G: Après recours à l’algorithme de Dijkstra, nous trouvons comme trajet le moins cher pour aller de l’aéroport A à l’aéroport G: le trajet A - E - D - C - G Et ce dernier coûtera: 45 + 40 + 60 + 50 = 195 €

Compilation réalisée à partir d’exercices de BAC TES

Exercice n° 1 Un groupe d’amis organise une randonnée dans les Alpes On a représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer Une arête entre deux sommets coïncide avec l’existence d’un chemin entre les deux sommets 1) a) Recopier et compléter le tableau suivant :

Tes Devoir surveillé n°6 : Exercice 1

Exercice 2 Une usine produit deux types E et F de moteurs Le bénéfice B, exprimé en milliers d’euros, pour une production journalière de x moteurs E et y moteurs F est : B x y x y x y22, 0,05 0,08 0,6 0,7 On admet que la production totale est vendue et que 0 10ddx; 08ddy 1 Calculer le bénéfice réalisé avec a

Correction Term ES spé Devoir Surveillé 3

Exercice 2 Un parc de loisirs décide d’ouvrir une nouvelle attraction pour les jeunes enfants : un parcours pédestre où chaque enfant doit recueillir, sur diﬀérents lieux, des indices pour résoudre une énigme Le parcours est représenté par le graphe ci-dessous

Corrigé du baccalauréat ES–L Antilles–Guyane juin 2016

[Corrigé du baccalauréat ES–L Antilles–Guyane \ juin 2016 EXERCICE 1 5 points Commun à tous les candidats 1 L’équation f (x)=0 admet exactement 2 solutions, la première sur [−1 ; 1] et la deuxième sur

MATHS APPLIQUEES A LINFORMATIQUE - Introduction à la théorie

Enfin, à titre d'exercice, nous proposons quelques problèmes et applications Nous encourageons vivement le lecteur à essayer de les résoudre afin de prendre la matière bien en main Le lecteur qui veut aborder ce chapitre devrait avoir : - une maîtrise élémentaire d'un tableur de type Excel ou OpenOffice,

Examen de Théorie des Graphes - epiportalcom

Dans cet exercice on ne considère que des graphes simples, planaires, et non-orientés Pour un tel graphe G = (V, E), on note n = jVjle nombre de sommets, e = jEj/2 le nombre d’arêtes, et f le nombre de faces Le degré moyen d’un graphe est 1 n å v2V deg(v) 1 (2pts) Justiﬁez que 3f 2e Réponse :

A B C D E F

0 6 9 11 5 9

6 0 3 6 5 2

9 3 0 0 4 4

11 6 0 0 5 6

5 5 4 5 0 8

9 2 4 6 8 0

a. Determine a minimum spanning tree with Kruskal's algorithm. b. Determine a minimum spanning tree with Prim's algorithm starting inF. c. Determine the shortest paths fromFto all other vertices by use of Dijkstra's algorithm. 2. Given a connected undirected graphGwith positive weights on the edges. By use of Dijkstra's algorithm, all shortest paths starting at vertexrhave been found. The union of these paths forms a tree, which we will call the Dijkstra tree atr. a. Give an example of a weighted graph, whose minimum spanning tree di®ers from all its Dijkstra trees. b. Prove that a minimum spanning tree and a Dijkstra tree ofGalways have at least one edge in common. 3. At each step of Kruskal's algorithm it has to be checked if the candidate edge creates a circuit. Think of a way to implement this, and deduce un upper bound for the complexity of the algorithm as a function of the number of vertices. 4. If some arcs of a directed graphDhave negative length, but no circuit has a negative length, then there exists a shortest path between any two nodes ofD. However,

Dijkstra's algorithm does not work anymore.

Give an example that illustrates this.

b. Why doesn't it help if we make all weights nonnegative by adding a constant to all given weights ? c.

Do these remarks also hold for Prim's algorithm ?

5. In a directed communication network, a message is send from a nodeato another nodeb. At each arc (i;j) of the network there is a probabilitypi;jthat the message will get lost on this arc. These probabilities are ¯xed and independent. The network manager wants to choose a path fromatob, such that the probability that the message gets lost on this path is minimal. Translate this problem into a shortest path problem. Can this problem be solved with Dijkstra's algorithm? 1

6.The table below gives the weights (lengths)w(x;y) of the arcs in a directed graph

(xcorresponds to the row, andyto the column).

A B C D E F

0 8 8 8 8 2

8 0¡2 7 6 2

8 4 0 3 2 3

8 4 0 0¡1 4

8 2 2 3 0 8

8 3 2¡1 4 0

a. Use the method of Bellman-Ford to determine a shortest path fromAtoC, or a negative circuit if such a path does not exist. b. Use the method of Floyd to determine a shortest path fromAtoC, or a negative circuit if such a path does not exist. c.

Same questions, but now withw(C;D) = 0.

2quotesdbs_dbs7.pdfusesText_5

[PDF] Exercises 1 Minimum spanning trees and shortest paths

A B C D E F

0 6 9 11 5 9

6 0 3 6 5 2

9 3 0 0 4 4

11 6 0 0 5 6

5 5 4 5 0 8

9 2 4 6 8 0

Dijkstra's algorithm does not work anymore.

Give an example that illustrates this.

Do these remarks also hold for Prim's algorithm ?

6.The table below gives the weights (lengths)w(x;y) of the arcs in a directed graph

A B C D E F

0 8 8 8 8 2

8 0¡2 7 6 2

8 4 0 3 2 3

8 4 0 0¡1 4

8 2 2 3 0 8

8 3 2¡1 4 0

Same questions, but now withw(C;D) = 0.