Una dintre cele mai mari provocari in informatica este sa gasesti solutii care ruleaza in timp polinomial la probleme care au pana acuma doar solutii nepolinomiale(ex. exponentiale), o problema clasica este determinarea circuitul hamiltonian intr-un graf, acesta trece prin toate nodurile grafului o singura data, exista o lista impresionanta de astfel de probleme pe partea de grafuri, o lista cuprinzatoare:
1 Like
Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)
Contine implementarea unui algoritm de determinare a componentelor conectate dintr-un graf o componenta poate fi privita ca un oras iar legaturile dintre orase ca si componente conectate foloseste ceva algoritm de parcurgere grafuri cu BFS, si stocheaza graful cu o matrice de adiacenta.
Google Maps foloseste grafuri in pathfinding dintre cei mai cunoscuti algoritmi de pathfinding este algoritmul Dijkstra, din cate am inteles din articol Google Maps foloseste o variatie de A*.