CODEWITHSUNDEEP
algorithmdirected-graph
AryaStark
AryaStark

Reputation: 43

Minimum weight edge in all paths of a directed graph

Given a directed graph with edges having -ve or +ve weights, what is the algorithms to find the smallest weight edges of all paths from vertex s to vertes d?

Upvotes: 0

Views: 1376

Answers (2)

mcdowella
mcdowella

Reputation: 19601

I would find all reachable from s, e.g. by depth first search. Then find all nodes that can reach d (equivalently, all nodes reachable from d in the graph with directions reversed). Now you want the smallest weight edges that start in the first set and end in the second set.

Upvotes: 0

thebenman
thebenman

Reputation: 1621

From Wikipedia

You are describing the Single Source shortest path problem. Which can be solved using Dijkstra's if the edges are only positive or Bellman-Ford if the edges are allowed to be negative as well.

The most important algorithms for solving this problem are:

  1. Dijkstra's algorithm solves the single-source shortest path problem.
  2. Bellman–Ford algorithm solves the single-source problem if edge weights may be negative.
  3. A* search algorithm solves for single pair shortest path using heuristics to try to speed up the search.
  4. Floyd–Warshall algorithm solves all pairs shortest paths.
  5. Johnson's algorithm solves all pairs shortest paths, and may be faster than Floyd–Warshall on sparse graphs.
  6. Viterbi algorithm solves the shortest stochastic path problem with an additional probabilistic weight on each node.

Upvotes: 1

Related Questions