Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
50 views

Djikstra algorithm analysis

My textbook says that the Dijkstra algorithm's runtime is $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that? Dijkstra algorithm pseudocode: ...
1
vote
1answer
29 views

How is Johnson's shortest path weighting function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ proven by the triangular inequility?

Recap to the Johnson's shortest path algorithm: By the procedure extending the original graph $G^\prime = (V^\prime, E^\prime), V^\prime = V\ \cup \{s\}, E^\prime = E\ \cup \{(s, v)\ |\ \forall v \in ...
0
votes
2answers
325 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 ...
0
votes
0answers
69 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 ...
3
votes
1answer
109 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 ...
2
votes
0answers
113 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: $$...
1
vote
1answer
34 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 ...
1
vote
2answers
410 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)$, ...
-1
votes
1answer
93 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 ...
2
votes
1answer
203 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 (...
1
vote
1answer
42 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 ...
1
vote
1answer
49 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 ...
1
vote
1answer
274 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 ...
2
votes
1answer
51 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 ...
1
vote
2answers
47 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 ...
1
vote
0answers
36 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 ...
2
votes
2answers
401 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 ...
1
vote
1answer
261 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 ...
2
votes
1answer
223 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 ...
-2
votes
1answer
483 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)...
0
votes
2answers
142 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 ...
1
vote
1answer
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 ...
0
votes
0answers
111 views

Intuition behind Floyd-Warshall being faster

I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm: Let $dp[i][j][n]$ denote the shortest path from $...
0
votes
2answers
63 views

Finding shortest path between two nodes with a set of forbidden nodes

I have undirected and unweighted graph, in which I would like to find the shortest path between two entered nodes. There is also a set of forbidden nodes. How to find the shortest path, if I am ...
1
vote
1answer
354 views

Behaviour of Dijkstra in Case of Negative Edge Weight [duplicate]

I came across a serious doubt regarding the implementation of the Dijkstra algorithm and hence wanted to discuss. For the given below graph What should be the Cost to reach Node G from Source Vertex ...
1
vote
1answer
50 views

Calculate Shortest Path (Shortest Time) Through a Store in a Graph

There is an undirected graph and some of the vertices are said to be stores. Person A wants to reach to person B with a present. That means person A has to stop by one of the vertices marked as stores ...
1
vote
1answer
131 views

Find shortest path for a volatile graph

Let me define a volatile graph first: It is an undirected graph in which the weight of each edge varies every time we query it. That is, when we request the weight w(e) of edge e, we obtain an ...
1
vote
0answers
46 views

Finding simple min-weight path between two vertices in graph with negative edge weights

Given a weighted graph (negative weights are allowed) and two vertices $u$ and $v$, can we find the simple min-weight path between $u$ and $v$? There can be a negative cycle on the path from $u$ to $v$...
1
vote
1answer
498 views

Confirmation of alternative correctness proof for Floyd-Warshall's all-pair shortest-path algorithm

The most common proof for Floyd-Warshall's algorithm is an induction proof on the outer-most loop, which says $\delta^k(i,j)=\begin{cases} \min\{\delta^{k-1}(i,j),\delta^{k-1}(i,k)+\delta^{k-1}(k,j)\}...
1
vote
0answers
99 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 ...
1
vote
1answer
248 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 ...
5
votes
1answer
234 views

Shortest path when allowed to reverse an edge

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 ...
2
votes
0answers
85 views

Shortest route through ordered points

My algorithm-fu is really weak and I do not know how to express following problem in terms of any other problem known to me: Given a small rectilinear grid and coordinates of four cells in this grid (...
1
vote
4answers
1k views

Chess Knight minimum moves to destination on an infinite board

There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm. Here is ...
2
votes
1answer
28 views

Travelling Problem with Constraints

Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance. You start your travel at a given node, say $1$, and end ...
1
vote
1answer
66 views

How do I solve a maze using velocity and acceleration?

I need to solve a maze. I can move an object around in a 2D maze by giving it 1 acceleration in any 8 of its 8 directions. The object starts at rest at 0 velocity. By only adding an acceleration at ...
1
vote
0answers
120 views

How to handle negative edge weights in distance vector routing protocol with a digraph?

In a Distance Vector routing protocol each node implements a Bellman-Ford inspired algorithm that shares it's routing table (Distance Vector) with each of it's incoming links (upstream neighbors). ...
1
vote
1answer
86 views

Recursive DP vs Graph Traversal solutions to path-based problems

I am studying some algorithms interview questions and I am seeing many path-based questions like "if a robot is at the top left of a grid and can only move down or to the right, how many paths can ...
3
votes
2answers
105 views

Is there a solution for this maze problem in polynomial time?

Suppose you have a maze represented by a graph where each vertex represents a room and edges represent paths between rooms and each edge has a weight denoting the time it takes to go that way. Now ...
3
votes
1answer
375 views

Modifying Floyd–Warshall Algorithm for Vertex Weights

I was trying to modify the Floyd–Warshall's algorithm to take into account the weights over the vertices, in addition to the weight of the edges, while computing the shortest path. The length of a ...
1
vote
1answer
65 views

Shortest path in a graph where edges are forbidden depending on the path taken

I have a problem similar to Shortest path problem where edge weight depends on path taken but not quite the same. In my case each edge has either a fixed finite weight, or an infinite weight, ...
4
votes
1answer
1k views

Finding all edges on any shortest path between two nodes

Given a directed weighted graph with non-negative weights, how can I find all edges that are a part of any of the shortest paths from vertex X to Y? In the example below the yellow edges are the ...
2
votes
0answers
121 views

Shortest path from one source which goes through N edges [closed]

In my economics research I am currently dealing with a specific shortest path problem: Given a directed deterministic dynamic graph with weights on the edges, I need to find the shortest path from ...
2
votes
1answer
58 views

How to find MST for each source

Let's say I have a map with factories and selling points. I want to trace the paths from factories to the selling points with the lower possible cost. The image bellow is an example of a possible ...
0
votes
0answers
20 views

Implementation/explanation of the hub based labelling algorithm

I've found plethora of papers describing the performance advantages and basic correctness proofs of the hub-based labelling shortest path algorithm. However I'd like to implement the algorithm, and ...
2
votes
2answers
75 views

Shortest travelling cost if we have bunch of points in 2D plane

I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane ...
6
votes
2answers
688 views

Finding the most efficient paths to cover an area from multiple starting locations

I'm looking to design an algorithm for a problem I have, and was hoping there may be someone that could provide some insight on where to start. In my picture above, the grid is the area they needs to ...
1
vote
1answer
197 views

Find shortest path in undirected graph that goes through all vertices and returns to starting vertex

I have an undirected weighted graph like this one My task is to find the fastest path (with least weight) that goes from specified vertex goes through all vertices and returns to the starting vertex ...
2
votes
1answer
40 views

Comparing nodes in A*

Nodes in the open list in A* will be sorted by their f-cost, but if the f-cost of two nodes are equal, will their h-costs instead be compared? I'm asking because I've seen implementations where the h-...
2
votes
1answer
91 views

LPA* implementation keeps looping

Short story I am currently trying to implement LPA* in an existing navigation system and find the algorithm seems to loop forever, expanding the same vertices over and over again. I am wondering what ...