# Questions tagged [shortest-path]

Questions about the algorithmic problems of finding shortest paths between nodes in a graph.

578 questions
Filter by
Sorted by
Tagged with
1k views

### Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?

Based on theory, the implementation using adjacency matrix has a time complexity of E+V^2 and the implementation using min heap has a time complexity of (E+V)logV where E is the number of edges and V ...
24 views

### Shortest path in a tree

Is it correct to talk about shortest path in a tree, isn't a tree has only single path between any two nodes ?
28 views

### Algorithm to efficiently plan a path to build a pixel structure

I have a problem that I have an unsatisfactory answer to and I would be interested in knowing if there is a better solution I am missing. The problem is as follows: Compute a series of ...
30 views

268 views

13 views

### What's the best way to combine multiple A* searches?

I have a graph that looks like this The highlights nodes must be visited, and the blue node must be visited last, the stickman must be the start of the path. The weights are the Euclidean distance ...
86 views

### Using A* path finding is giving me inaccurate results

So I am using A* pathfinding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of ...
33 views

### The shortest path that visits every specified node before finally reaching the specified end node?

After asking another question(Is the last step in the Christofides' algorithm necessary), I have decided Christofide's algorithm probably doesn't solve the problem I'm facing. Is there any ...
349 views

### Shortest path that can be split into contiguous segments of 5 edges connecting 6 distinct nodes in an unweighted graph

The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics: Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. ...
63 views

### What is the significance of Bellman-Ford and linear programming for scheduling and makespans?

CLRS exercise 24.4-9 says the following: Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity \$\max_i\{x_i\...
61 views

### Vertices reachable from negative-weight cycles in Bellman-Ford

TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-...