graph theory

4 articles · All tags

• The Traveling Salesman Problem: Why the Shortest Route Is Hard
  The traveling salesman problem asks for the shortest route that visits every city once and returns to the start, simple to state but very hard to solve.
• Breadth-First Search
  A graph traversal algorithm that explores vertices in order of distance from a source using a queue, finding shortest paths in unweighted graphs.
• Bellman–Ford Algorithm
  A single-source shortest path algorithm that handles negative edge weights and detects negative cycles, running in O(V×E) time.
• Dijkstra's Shortest Path Algorithm
  A greedy graph algorithm that finds the shortest paths from a single source vertex to all others in graphs with non-negative edge weights.