# Questions tagged [shortest-path]

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

474 questions
Filter by
Sorted by
Tagged with
1k views

### Shortest path with positive edge cycle

When reading about shortest paths in Cormen . I came across this paragraph which says that 'shortest path cannot contain' positive edge path even. But I don't understand the logic behind their ...
294 views

### Shortest path with minimal blue edges

Let $G=(V,E)$ be an undirected graph,such that ever $e\in E$ has a color-blue or red. Given $G$ and some $s,t\in V$ ,find an efficient algorithm that find from all pathes from $s$ to $t$,one with ...
90 views

### Is it possible that the diameter of a graph be shorter than the longest shortest path?

I used networkx to find the diameter of a graph that I have. It gave a diameter of 4. However, I found that between two particular nodes, using networkx's shortest path function, the path length is 5. ...
514 views

### Perform Dijkstra on graph with negative edges by adding a big enough constant to every edges

I know that this doesn't work because shortest path with a lot of edges may have bigger weight than a longer path with less edges. But what if, you keep track of the edges that our current weight path ...
103 views

### Prove that every two vertices in graph are connected by a path of some length

I'm working on simulating a network architecture. I'm representing every node and their connections as a connected graph with no directional edges. I need some help with my reasoning. Every node in ...
2k views

### How to backtrack the shortest path in BFS based shortest path calculation? [closed]

I understand how BFS can give the shortest path in a graph but I am not able to code the entire thing. The part where I am stuck is when I pop a node from the queue and see that its the target node, ...
194 views

### Sum of all distances in connected DAG in $O(n\log n)$

I have a DAG with $n$ nodes and $n-1$ edges. The edges in DAG (fixed) are defined as follows: For every node $i$, $1 \le i \le n-1$ is connected to node $i+1$. The lengths of the $n-1$ edges are ...
3k views

### Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties?

I am trying to understand some notes regarding the A-star algorithm. The example used is to show how the algorithm can be used as a (more efficient) alternative to Dijkstra's algorithm for finding ...
289 views

### Looking for an algorithm to find a shortest path in a special graph

I have the following problem: given a directed unweighted graph and a set of source vertices, it's needed to find the shortest path to the specified vertex. The mentioned graph has two special ...
1k views

### Finding the Shortest Path that connects k nodes in a graph

I was wondering if there are algorithms for finding the shortest path that contains some selected $k$ nodes in a weighted graph. More specifically, the path that we are looking for needs to pass ...
65 views

### Shortest past including an edge from a given set

I am working on the following problem. There are N vertices and M roads connecting them. Some of the roads are broken. I have to go from vertex 1 to vertex N taking at least one good road and find ...
51 views

### Pathfinding when the graph varies over time

Let's say I want to simulate a very large number of travelers booking flights. For example, a traveler might want to fly from New York to New Delhi. There's no direct flight from New York to New Delhi,...
940 views

### Linear programming formulation for the single-source shortest path problem

In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP): \begin{align} \max &\sum d_u \\ \text{subject to} & \\ d_v &\le ...
98 views

### Combining Runtime Complexity Expressions with respect to Dijkstra

If I have an algorithm that fills out an $|V| \times |V|$ table with for loops and an $O(1)$ sub-problem after running Dijkstra twice (outside the loop), I think I get the following runtime complexity ...
502 views

### Edge weight changing during execution in shortest path algorithm

I have an undirected graph with weighted edges, in which I want to find the shortest paths from an initial node to every other node. Obviously Dijkstra's algorithm is usually a good choice, and I have ...
149 views

### State-of-the-Art techniques on dynamic shortest path computations

Suppose that I would like to find the shortest path between two vertices in a dynamic graph, where the cost function of an edge changes occasionally. I understand that an efficient algorithm to target ...
468 views

### Bellman-Ford: Find all nodes that have minus infinite distance to source

Given a weighted, directed graph (V, E) may contains some negative cycles and a source node s, I would like to know for all node ...
394 views

### Algorithm to traverse all unblocked $1*1$ squares in a $n*m$ grid

Given a $n*m$ grid, some $1*1$ squares are blocked(can't be entered) and some are unblocked(can be entered). What is the algorithm which prints the shortest path, such that the path covers all ...
2k views

### Minimum-weight shortest-path tree

How can we compute the shortest-path tree of minimum total weight for a given connected graph? I am using Dijkstra's algorithm to find the shortest-path tree, but there may exist more than one ...
66 views

### Adapting Dijkstra to list all shortest paths [duplicate]

I found a code in the internet for Dijkstra's shortest path algorithm in PHP. The problem is it only shows one possible path. If there are several paths having the same distance, it only outputs one ...
421 views

### Running Time of naive implementation of Dijkstra's Algorithm

Here is the "naive" implementation of Dijkstra's algorithm that the professor uses: For a directed graph $G = (V,E)$ as input Initialize: $X = \{s\}$ (the vertices processed so far) ...
330 views

### Optimality in multi-agent multi-target path finding

Suppose I have a regular rectangular weighted grid with multiple agents and obstacles. Agents cannot be in grid sites that contain obstacles, and for simplicity assume multiple agents can be in the ...
1k views

### All Pairs Shortest Path vs Shortest Path [closed]

I do not understand the difference between the All Pairs Shortest Path problem (solved by the Floyd–Warshall algorithm) and the Shortest Path problem (solved by Dijkstra's algorithm).
1k views

### Shortest walk through a given subset of edges

Given an undirected weighted graph $G = (V, \{E,F\})$, how to find the shortest walk that passes through all edges $e \in E$ exactly once? I'd like to know if there is a general approach to this ...
780 views

### Modification of Dijkstra's algorithm

How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality? There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough ...
157 views

### Trouble implementing back-tracking in RBFS

I'm trying to implement an rbfs search algorithm for the 15 puzzle (pseudo code below). link to the paper where i found the pseudo code: https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/viewFile/...
307 views

### Mean and median distance in unweighted graph

I have a very large graph of ~7 million vertices and ~100 million edges. One dfs run in my current implementation runs in 30 seconds. The graph is an unweighted directed strongly connected graph. I ...