Exact algorithms in data structures and graph theory

Question

In data structures and algorithms, what is meant by "Exact Graph Algorithms"? Can you give me some examples?

Answer 1

I suppose it refers to whether the algorithm yields a result, that is optimal for a given problem or if it yields "just" an approximative result.

For example, if you are looking in a graph for the shortest path from one node to another, there are a bunch of algorithms (Dijkstra, Floyd-Warshall,... you name them) that solve the problem exactly, i.e. they yield a shortest path between the two given nodes.

On the other hand, consider the Travelling Salesman problem. It states the question of a shortest circular path containing some given nodes. This problem is NP-complete, and thus (supposedly) not solvable exactly in a reasonable amount of time (at least for the general case). However, there exist approximation algorithms running in reasonable amount of time, that yield a solution that is at most 2*length(best route) (at least for metric TSP), so the solution from this algorithm is not an exact one, but just an approximation.