Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

--- laboratoare:laborator-07 [2017/04/01 19:34]
mihai.iacov [5. Observaţii finale]
+++ laboratoare:laborator-07 [2017/04/07 16:55]
iulian.matesica [6. Exercițîi laborator]
@@ Linia 1: / Linia 1: @@
-====== Laborator 07: Parcurgerea grafurilor ======
+====== Laborator 07: Drumuri de cost minim ======
 ===== 1.Obiective laborator ======
@@ Linia 195: / Linia 195: @@
 </note>
-===== 6.Exiciții laborator ======
+===== 6. Exerciții laborator ======
+  - Daţi un exemplu de graf orientat cu un singur arc cu cost negativ pentru care algoritmul lui Dijkstra dă rezultate greşite.
+  - Cum putem folosi algoritmul lui Dijkstra sau algoritmul Bellman-Ford pentru a obţine aceleaşi rezultate ca algoritmul Floyd-Warshall(drumul de cost minim pentru toate perechile de noduri)? Ne limităm la grafurile pe care merg toţi cei trei algoritmi.
+  - Implementaţi unul din algoritmi pentru a calcula drumurile de cost minim de la un nod sursă la toate celelalte noduri într-un graf cu toate muchiile/arcele cu cost pozitiv.
+  - Verificaţi dacă un graf conţine cicluri negative.
+====6.1. Exerciții - schelet de laborator====
+Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab7_drumuri_minime-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.
+=== Linux===
+Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
+  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab7_drumuri_minime-skel.zip%%''
+  * ''%%unzip lab7_drumuri_minime-skel.zip%%''
+Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./graph%%''.
+===Extra===
+  - Se dă un graf pentru care se cunoaşte drumul de cost minim de la un nod sursă(S) la un nod destinaţie(D). Dacă adăugăm 100 la costul fiecărei muchii, se modifică drumul de cost minim? (dacă da, daţi un exemplu; dacă nu, explicaţi de ce).
+  - Aceeaşi întrebare dacă înmulţim fiecare cost cu 100.
+  - Cum găsiţi(mai rapid decât cu cei 3 algoritmi prezentaţi) drumul de cost minim de la S la D într-un graf în care toate muchiile au acelaşi cost(1)? Cum adaptaţi soluţia în cazul în care toate muchiile au costul 1 sau 2?
+  - Daţi un exemplu în care folosirea algoritmului lui Dijkstra(pentru a obţine drumul de cost minim pentru toate perechile de noduri) ar fi mai rapidă decât algoritmul Floyd-Warshall.
 ===== 7.Referințe ======

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină