0

Given some undirected and edge-weighted graph, what algorithm can be used to find the shortest path from some vertice v to another vertice w?

For a directed edge-weighted graph, you could use Dijkstra's shortest path algorithm, but I am working with an undirected graph, so it won't work.

For a graph that is not edge-weighted, you could use breadth-first search (BFS), but I am working with an edge-weighted graph, so it won't work.

So given that it is both undirected and edge-weighted, what is the general shortest path method?

0jnats3
  • 85
  • 1
  • 7
  • what makes you think that you cannot use Dijkstra's algorithm for undirected graphs? – mangusta Oct 06 '19 at 19:41
  • @mangusta In the book I am reading (Algorithms 4th ed. by Sedgewick), the section on shortest paths brings up Dijkstra's algorithm specifically for directed graphs. Their proposition: Dijkstra’s algorithm solves the single-source shortest-paths problem in edge-weighted digraphs with nonnegative weights. – 0jnats3 Oct 06 '19 at 19:44
  • 1
    the author probably considered undirected graphs as digraphs with edges `i -> j` and `j -> i` for every pair `(i , j)` having an undirected edge between them – mangusta Oct 06 '19 at 19:48
  • @mangusta I can barely find any resources online where undirected graphs are mentioned together with Dijkstras. Either way, is it possible to modify breadth first search to account for edge weights when finding the shortest path? – 0jnats3 Oct 06 '19 at 19:53
  • of course not. you can use Dijsktra's algorithm for a general undirected graph. – mangusta Oct 06 '19 at 19:55
  • @mangusta What do you mean of course not? Why is it not possible to use BFS for an edge-weighted undirected graph? Would you not consider it BFS anymore if you modified it to take into account weights of edges? – 0jnats3 Oct 06 '19 at 19:58
  • same reason why it is not possible to turn wood into gold, lol. the aim of bfs is completely different from finding a shortest path. if no weights, shortest path can be calculated as a side effect of bfs – mangusta Oct 06 '19 at 20:00

1 Answers1

1

Dijkstra's single-source shortest path algorithm can be applied on both undirected and directed graphs. The only stipulation is that the edge weights must be non-negative. Starting from a single vertex v in a graph, v is popped into a set S. The algorithm checks each adjacent vertex not already in S, picks the edge with the smallest weight, and pops that vertex into S. The distance from vertex v to each adjacent vertex in S is updated based on the edge weights. Once the entire graph has been traversed, the shortest path between each node has been determined.

Example: https://brilliant.org/wiki/dijkstras-short-path-finder/

In addition, performing BFS on a weighted-edge graph proves to be intractable. See this post regarding the reasoning.

Zach Taylor
  • 11
  • 1