Find path in undirected graph

Statement

Find path between vertices in an undirected graph

Given an undirected graph and two vertices . How can we find a path in between them. Sometime we will also have a weighting and we want to minimise the path length.

Solutions

• DFS to find path in an undirected graph
  • This runs in .
  • This doesn’t use weights.
  • This doesn’t get the shortest path.
• Bellman-Ford algorithm
  • This runs in .
  • This works for weights finding the shortest path.
  • This find negative cycles.
• Floyd-Warshall algorithm
  • This runs in .
  • This works for weights finding the shortest path.
  • This finds paths between all vertices.
  • This find negative cycles.
• Dijkstra’s algorithm
  • This runs in (using the Min-heap data structure).
  • This words for weights finding the shortest path.
• BFS
  • This runs in .
  • This doesn’t use weights.
  • This gets shortest paths from a root vertex.