Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
14 views

C++ finding the shortest path, reducing time complexity, dijkstra v Floyd Warshall Algorithm?

I have an algorithm that I am performing on a graph and I am looking to do an analysis of how to speed it up and would appreciate any comments. The algorithm iterates over every edge in the graph. ...
44
votes
7answers
64k views

Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
0
votes
0answers
11 views

APSP on GPGPU with paths reconstruction

There is a huge number of works on efficient solution of all-pairs shortest paths (APSP) by using GPGPU. But the main goal of these works is to compute the length of the shortest path. Are there exist ...
0
votes
1answer
223 views

How to deal with cost variation in a dynamic graph when applying Dijkstra

What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I ...
1
vote
1answer
290 views

Find a path that contains specific nodes without back and forward edges

I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...
2
votes
0answers
40 views

Similar-path shortest paths

Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $n$ as the number of vertices, that the number of edges ...
1
vote
1answer
561 views

Routing algorithm for train network

I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges ...
2
votes
2answers
62 views

A* without heuristic more efficient than Dijkstra

I am using the module networkx to operate on graphs made from OpenStreetMap. I wanted to compare the shortest path algorithm to ...
0
votes
0answers
34 views

Graphs - Shortest Path Algorithms - Summary

Are following statements valid? Shortest Path in an undirected graph can be found using BFS. Is DFS an option here? If DFS is not an option, why. Dijkstra's SPT works if there are no negative ...
0
votes
0answers
17 views

How to guarantee the minimum path removed from priority queue is the shortest path after all infinite vertices relaxed

I readed the proof of Dijkstra's algorithm in "CLRS",and the code in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. Figure 24.7 in CLRS proofs the correctness of Dijkstra's algorithm. ...
2
votes
3answers
64 views

Shortest path between any origin to any destination through some way stations

How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm? You can visit those way stations ...
1
vote
1answer
57 views

Minimum distance of nodes from a set of two nodes

In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
2
votes
1answer
33 views

Thorup : What is the meaning of super distance?

While reading Thorup's Algorithm to solve SSSP problem, I have one point that I can't understand: super distance. It says: "For each vertex we have a super distance $D(v)\geq d(v)$" $d(v)$ must ...
0
votes
1answer
22 views

Using the decision problem, PATH in order to solve the optimization problem, SHORTEST-PATH in polynomial time

So, if I were using a black-box decision algorithm, PATH in which I could say, "does a path of weight k exist in this graph from ...
-2
votes
2answers
461 views

When is bidirectional search unusable?

Is there any situation that bidirectional search on a graph is not applicable? for example is there any classes of graph that we can only use ordinary Dijkstra's algorithm, and can not use its ...
1
vote
1answer
32 views

calculating a shortest path in a table structure that changes in real time

I have a table that looks like this In table NPC - are AI like characters that move from one point to another. Player - a character that is controlled by the user. In any moment the player ...
2
votes
0answers
33 views

Given complete graph, find optimal path with two costs on each edge

We are given complete graph, such that each edge has two costs $a \text{ and } b$. We should find path that passes through each node once and has minimum total cost. Cost of a path is the maximum of ...
1
vote
1answer
55 views

Shortest path in a incomplete graph

I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
11
votes
6answers
38k views

Why can't DFS be used to find shortest paths in unweighted graphs?

I understand that using DFS "as is" will not find a shortest path in an unweighted graph. But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? ...
3
votes
2answers
118 views

Single-source shortest paths with even weight

I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even. In another words, we have to find the ...
0
votes
0answers
21 views

Single source shortest paths with even path [duplicate]

Given directed graph with non negative weights and vertex s. I need an algorithm that finds shortest paths from s to all vertices and the paths have to be even.
0
votes
0answers
69 views

Shortest path for vehicle routing problem with alternative locations

I'm currently developing an algorithm that solves the vehicle routing problem with time windows and the possibility for clients to be delivered to multiple locations. Right now, I'm trying to find ...
2
votes
1answer
129 views

Proof that shortest path with negative cycles is NP hard

I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is ...
1
vote
1answer
95 views

Shortest Path in Layerwise Complete Graph

Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. ...
1
vote
0answers
18 views

Can the shortest path problem be solved using Monte Carlo Tree Search?

I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step. If we consider the path ...
0
votes
1answer
35 views

Confused in calculating the shortest-path using Dijkstra's Algorithm [closed]

I am required to find the shortest path using Dijkstra's Algorithm. After performing the calculations, am I getting the following values correct?: ...
11
votes
3answers
1k views

What is the meaning of 'breadth' in breadth first search?

I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this: Breadth-...
1
vote
2answers
76 views

Shortest path with a given condition

The problem says to find the shortest way (the smallest amount of intermediary points), with given source and destination points, such that between two consecutive intermediary points there are two ...
6
votes
1answer
409 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
2
votes
1answer
47 views

Bellman-Ford - is number of interations greater than diameter?

Diameter of a connected, undirected graph is the smallest natural number d, so that between any two vertices of the graph exist path of length at most d. Prove or disprove: in Bellman-Ford is ...
1
vote
1answer
44 views

Is the number of shortest paths between every two vertices at most 4*n^3?

In every weighted graph with $n$-vertices with negative weights, with $n > 10$, a weight can't appear $n$-times in graph, there are between every two vertices at most $4n^3$ shortest paths. I'm ...
1
vote
0answers
58 views

Finding negative cycle using Bellman Ford

Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph. The wanted complexity is O(|V|*|E|). I was thinking about using Bellman-Ford to solve the ...
2
votes
1answer
47 views

shortest path tree algorithm

Suppose we are given a directed weighted graph $G=(V,E)$, a source vertex $s$ and the value of the cheapest path $\delta(s,v)$ for every $v \in V$. I want to find an algorithm for the shortest path ...
0
votes
1answer
63 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 ...
4
votes
1answer
100 views

Path between two vertices in directed graph without cyclic vertices

I have been searching online for some time but I have not found an answer. Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no cyclic ...
3
votes
2answers
506 views

Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...
0
votes
0answers
28 views

Implementation of multiple sink shortest pair of disjoint paths problem for multigraphs

I would like to implement the shortest pairs of edge-disjoint paths of Suurballe and Tarjan for multigraphs in the interpretation of Banerjee et al. (http://web.cs.iastate.edu/~pavan/papers/short.pdf, ...
1
vote
1answer
181 views

Djikstra's algorithm to compute shortest paths using at least k edges

I have a graph G = (V, E) where each edge is bidirectional with positive weight. I want to find the shortest path from vertex s ...
2
votes
1answer
251 views

Multiple Source Shortest Paths in a weighted graph

In an unweighted graph, we can find Multiple Source Shortest Paths using the Breadth-First Search algorithm by setting the distance of all starting vertices to zero and pushing them into the queue at ...
0
votes
1answer
51 views

Minimal paths as solution of a linear program of a special network flow

Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$. We're looking for the shortest ...
6
votes
1answer
143 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 ...
0
votes
0answers
154 views

How can an A* algorithm visit all nodes?

Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?
2
votes
1answer
142 views

Given directed connected weighted graph, check if d(v) = delta(s,v)

I'm having some hard time with this problem. Can someone give me some clue/guidance? This is an homework question, so please don't just solve it. Given a weighted directed connected graph $G = (V,...
1
vote
1answer
206 views

Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis

Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best ...
4
votes
0answers
83 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 ...
0
votes
1answer
17 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 ...
1
vote
1answer
203 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 ...
1
vote
1answer
291 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 ...
3
votes
1answer
118 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 ...
2
votes
2answers
177 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 ...