Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1

by

This is laborous case work:

  1. A < B and 0 and N-1 are joined by A -> trivial.
  2. B < A and 0 and N-1 are joined by B -> trivial.
  3. B < A and 0 and N-1 are joined by A ->
    Do BFS on graph with only K edges.

  4. A < B and 0 and N-1 are joined by B ->
    You can check in O(N) time is there is a path with length 2*A (try every vertex in middle).

    To check other path lengths following algorithm should do the trick:
    Let X(d) be set of nodes reachable by using d shorter edges from 0. You can find X(d) using following algorithm: Take each vertex v with unknown distance and iterativelly check edges between v and vertices from X(d-1). If you found short edge, then v is in X(d) otherwise you stepped on long edge. Since there are at most K long edges you can step on them at most K times. So you should find distance of each vertex in at most O(N + K) time.

More Related Contents:

  1. Finding all the shortest paths between two nodes in unweighted undirected graph
  2. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  3. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  4. Negative weights using Dijkstra’s Algorithm
  5. How does Dijkstra’s Algorithm and A-Star compare?
  6. Find cycle of shortest length in a directed graph with positive weights
  7. graph – Dijkstra for The Single-Source Longest Path
  8. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  9. Find all paths between two graph nodes
  10. Cycles in an Undirected Graph
  11. Breadth First Vs Depth First
  12. Millions of 3D points: How to find the 10 of them closest to a given point?
  13. Find the shortest path in a graph which visits certain nodes
  14. How to trace the path in a Breadth-First Search?
  15. Graph auto-layout algorithm
  16. Find connected components in a graph [closed]
  17. Performing Breadth First Search recursively
  18. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  19. Algorithm for “nice” grid line intervals on a graph
  20. How to implement depth first search for graph with a non-recursive approach
  21. Longest acyclic path in a directed unweighted graph
  22. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  23. Why is the time complexity of both DFS and BFS O( V + E )
  24. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  25. Enumerating all paths in a directed acyclic graph
  26. Why does Dijkstra’s algorithm use decrease-key?
  27. Planar Graph Layouts
  28. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  29. Finding connected components of adjacency matrix graph
  30. Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)

Leave a Comment