# Questions tagged [shortest-path]

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

472 questions
Filter by
Sorted by
Tagged with
84 views

### Can the running time be reduced to something lower than $O(d^4)$?

Imagine I have a weighted complete directed graph $G$ with $d$ vertices(so $d(d-1)$ edges) and I want to do the following: Set $D$ to be a DAG with the same set of vertices but without any edges sort ...
18 views

### Term for an A*-like pathfinding strategy where only the heuristic goal distance matters

I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance ...
99 views

### Hitting probability of random walk within given number of steps

Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates. What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially? We can ...
321 views

### Floyd–Warshall algorithm on an undirected graph contains negative weight edges

According to this answer, the Bellman-Ford algorithm doesn't work when an undirected graph contains negative weight edges since any edge with negative weight forms a negative cycle, and the distances ...
158 views

### Finding a negative cycle in a bipartite graph

The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where ...
63 views

### Distance function such that we visit every “color region” once [closed]

Consider the following image: Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right. We must go through each color exactly once, and once we go outside a color, ...
144 views

### Constructing a minimum spanning tree from an all-shortest path graph?

Given an $n \times n$ shortest path distance matrix $D$. And a complete graph $G(D)$ on $n$ nodes, where edge $(i, j)$ has weight $D_{ij}$. Furthermore, the distance matrix $D$ is computed for a ...
63 views

### Combinatorial Optimization: Shortest distance given sets of drivers and riders

Problem: I have 2 sets, one of drivers and one of riders. All my participants need to reach one common destination. I wish to calculate the shortest combined distance in order for all participant to ...
391 views

### Given all pairs shortest paths matrix, find graph with minimum total sum of edges

I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some ...
619 views

### How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs

The Bellman-Ford algorithm on a graph with $n$ vertices, normally includes a loop executed $n-1$ times. Each time through the loop we iterate over the list of edges $(u,v)$ and relax $v$. Note that ...
60 views

### All pair shortest path in a tripartite graph

I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination ...
30 views

### Longest simple walk below a certain weight

Given a directed graph G and a starting vertex $v$ and a cutoff weight $w$, I want to find a simple walk with net weight < $w$ that visits as many nodes as possible. Currently, I have a recursive ...
81 views

### Running Dijkstra on particular graph with negative weight

After running Dijkstra on this graph from S, which shortest paths will be incorrect? This graph has a negative weight, so which shortest paths will be incorrect? after my first attempt I got that Y ...
543 views

### Dijkstra complexity analysis using adjacency list and priority queue?

I just got to look at the Implementation of Dijkstra using adjacency list and priority queue. The time complexity is $O(E\log V +V)$, I tried looking for the proof but couldn't find one. Any help will ...
45 views

528 views

### Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal

In CLRS, in the later part of breadth first search topic, for unweighted graphs, it says: At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable ...
177 views

### Finding all edges on any shortest path between two nodes using dijkstra

Given a directed weighted graph, we need to mark all edges (represented by an ordered triple of (source,destination,weight) ) which lie on some shortest path from source to destination (there could be ...
190 views

### Intersection of two shortest paths in connected weighted graph

Let $G=(V,E)$ be a connected directed weighted graph with non-negative weights on edges. Let $u,v,s,t$ be vertices in the graph $G$. I need to find an algorithm which in $O(|E|\log |V|)$ time checks ...
130 views

### Why is it true that given a monotonic heuristic function, A* can be seen as Dijkstra's algorithm where no node needs to be processed more than once?

Maybe I am missing something very easy and obvious. But, I don't understand why estimate cost of source vertex is subtracted from the overall estimate cost, if heuristic function $h$ is monotonic: ...
37 views

### Shortest path in graph by flipping binary colored nodes to one color [closed]

Given a graph consists of two-colored nodes(e.g. white and black) and a starting node, and every time you visit a node, its color is switched(from black to white, or, white to black), how to find the ...
546 views

### Time complexity of Dijkstra's algorithm for sparse graph

I'm not sure I understand the answer to this question: Question 9. What is the running time of Dijkstra's algorithm in a graph that is sufficently sparse - in particular, $E=o(V^2/\log V)$, ...
98 views

### Computer Networks, OSI model

What layer of OSI model does define the route of information transmission between sender and receiver computers? A) Session layer B) Physical layer C) Data link layer D) Network layer E) Transport ...
425 views

### Confused about the correctness proof of Dijkstra's algorithm

In the proof of the correctness of Dijkstra algorithm, there is a lemma stating as follow: Let u be v's predecessor on a shortest path P:s->...->u->v from s to v. Then, If d(u) = δ(s,u) and edge (...
45 views

### What's the usage of $S$ in Dijkstra shortest path algorithm in the book Introduction to Algorithms?

I don't understand how the $S$ is needed in dijkstra shortest path algorithm. For each node $v$ in $G.V$, the $v.\pi = previous\_node$ is used to denote it previous node in the shortest path to the ...
82 views

### Will MST find the shortest path for each pair $(r,v)$?

Will local best choice will lead to global best choice? In other words, I'm thinking about whether it's possible that the MST has to put its branch location in the middle of two far nodes ...
351 views

### Word ladder problem for words with different length

Is there some one who know any algorithm for word ladder problem with words of different length? Actually we have some strings with same length and some strings with one length longer but not from ...
61 views

### Shortest path with nodes containing collectibles of negative cost

Suppose you have a graph with weighted edges and nodes. Edges always have non-negative costs (representing e.g. fuel costs), and nodes always have non-negative benefits (representing e.g. collectible ...
60 views

### Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights

Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for ...
39 views

### Concurrent Shortest Paths with “Congestion Penalty”

Given a graph with positive edge weight representing "time to travel through", and 2 or more pairs of start/end vertices, we can find concurrent paths for the pairs such that the maximum cumulative ...
523 views

### Find shortest path that goes through at least 5 red edges

Let $G=(V,E)$ be a directed graph, $\omega : E \rightarrow R$ a weight function, and $s,t \in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Moreover, 10 of its edges ...
432 views

### Dijkstra’s shortest path algorithm

I'm learning about single source shortest path algorithms and need to clarify few doubts- Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers. Does ...
439 views

### Shortest path with a start vertex that touches all nodes at least once with repeats allowed

I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I ...
653 views

### Please indicate whether each of the following statements is TRUE or FALSE and provide a brief justification

I provided my answers in the "answer your own question" bit. I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though? a)...
203 views

### Shortest distance from multiple points to one point

I am looking for an algorithm to find the shortest distance from multiple nodes to one end node. For example let $v_1,v_2,\dots,v_r$ be the nodes on a graph with distance $d_1,d_2,\dots,d_r$ to the ...
42 views

### What happens if I replace $<$ with $\le$ in Dijkstra's algorithm?

The following is Dijkstra's algorithm for finding the shortest path in a graph. I know something wrong happens if I replace d[u] + weight(u,v) < d[v] with ...
137 views

122 views

### Minimizing cost of shortest paths to a group of vertices by adding minimal edges to an unconnected vertex

Let $G=(V,E)$ be directed graph, where the weights of the edges are non-negative. The graph might have cycles, but without parallel edges. Consider a $T \subset V$, and $u \notin V$. I'm trying to ...
317 views

### Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
We're given an unweighted directed graph with vertices $V$ and edges $E$. We're trying to find the shortest path from $s$ to $t$ but we're allowed to travel along up to one edge in the ...