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
134 views

Modified shortest path problem

For a given graph $G=(V,E)$ and a given weight function $W$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $w^*(p)=\varSigma(w(v_i,v_{...
2
votes
0answers
26 views

Is there a Dijkstra like pathfinding with condition satisfication algorithm?

Say we have a place-transition digraph system. A transition can fire if all input places have marks. A transition fires by consuming items from input places and placing one into each output place. A ...
0
votes
1answer
148 views

Create an algorithm for computing the shortest path in O(m + nlogn)

So I'm trying to write an algorithm for computing the shortest path with constraints on the vertices you can visit in $O(m + n \log n)$ time. In this problem, we are given an indirect weighted (non ...
0
votes
1answer
171 views

find shortest paths from source to all vertices using Dijkstra’s Algorithm?

For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph but how can i calling the algorithm |V| times taking each vertex as a source and store all tables ??? For ...
0
votes
0answers
30 views

Bellman-Ford - If an edge was relaxed one more time then there is a cycle in parent pointers

I was given an exercise to prove that the Bellman-Ford algorithm, with maintaining a predecessor array for the vertices, allows finding a negative weight cycle in the graph. I should emphasize that ...
1
vote
1answer
182 views

Minimum bottleneck path between two vertices in an undirected graph

I have an undirected graph, where the value of the path is the maximum weight among all weights edges included in it. And I want find the path of minimum value between two given vertices in time $O(n ...
0
votes
0answers
25 views

Is It Of Much Practical Use To Actually Use Fibonacci Heap Over Min Heap In Dijkstra Algorithm?

I know that to get the best technical running time in Dijkstra's shortest path algorithms, using a Fibonacci Heap is the correct way to go. However, the internet and in CLRS state that Fibonacci Heap ...
1
vote
1answer
33 views

Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria

I'm putting together a personal list of recipes that I enjoy, and would like to construct an algorithm that parses this recipe database and automatically builds me a meal plan for the week. For N ...
1
vote
1answer
45 views

How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path

I have a directed graph that has positive weights (but there are reverse arcs) and I am trying to find the shortest path between a given source, s and a given sink, ...
2
votes
1answer
504 views

Gas Station Problem - Dijkstra's Algorithm variation

I am trying to find an algorithm which finds the least expensive route from one town to another. This is the general setup. There are a series of one-way roads from some towns to other towns. Not ...
2
votes
0answers
103 views

For which class of graphs can a minimum spanning tree always be associated to a shortest path tree?

Given a connected graph $G=(X,E)$ with positive edge weights. We assume that $G$ contains a unique min weight spanning tree $T_{\min}$ (this is true for example when for all the cuts, the edge with ...
1
vote
0answers
236 views

Johnson's vs Floyd-Warshall for dense graphs

I often read that Floyd-Warshall is a good fit for dense graphs and Johnson's for sparse ones. While it's easy to see why Johnson outperforms Floyd-Warshall on sparse graphs, I'm noticing that ...
1
vote
1answer
75 views

How Do You Design an Algorithm for This Graph

Introduction I'm not really understanding my algorithms class. One of our HW assignments is to design an efficient algorithm for this graph Questions Give an efficient algorithm to find the fastest ...
0
votes
1answer
31 views

What Is The Appropriate Action To Take When You're Shortest Path Algorithm Finds A Negative Weight Cycle?

Typing out negative weight cycle again and again is kind of annoying, so for the rest of the question I'm going to abbreviate it to NWC. I'm writing an optimized version of Bellman-Ford's Shortest ...
0
votes
2answers
45 views

Is There Any Shortest Path Algorithm That Finds The Shortest Path Between Only Two Nodes

The Dikstra shortest path algorithm on a weighted graph, directional or bidirectional, pretty quick. There is also the Bellman Ford algorithm. However, these two find the shortest path between one ...
0
votes
1answer
42 views

Shortest path form node X to nodes A, B, C in graph

I have an unweighted consistent graph and some node X(the source) and some nodes A, B, C and more. I need to find the shortest paths: X->A, X->B, X->C and ...
2
votes
1answer
36 views

Raptor algorithm: find next best paths

I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). What are the ways to find next best paths (path is a sequence of trips and transfers from source to ...
3
votes
1answer
92 views

Dijkstra algorithm modification with exactly one relaxation on a directed graph where the weights of outgoing edges of a node are the same

Consider the standard version of Dijkstra's algorithm on directed graphs. Assume it is known that the input digraph $G = (V, E)$ has the following property: for all $v \in V$ the weight of all ...
1
vote
0answers
16 views

Queries on unbounded knapsack

Given $n$ types of items with integer cost $c_{i}$ (there is an unlimited number of items of each type), such that $c_{i} \leq c$ for all $i = 1, 2, \dots, n$, answer (a lot of) queries of form "is ...
2
votes
0answers
31 views

Finding multiple paths through a grid such that every grid square is equally used

Setup Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number ...
0
votes
0answers
56 views

Least-weight path in a DAG--why not just use Dijkstra?

I have an assignment to find the least-weight path in a DAG from a source to a target. But the class has already discussed Dijkstra's algorithm, so I'm wondering, why not just use that? It seems too ...
1
vote
1answer
60 views

A pathfinding algorithm for graphs in which arc weights can change over time

So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction. Here's the situation, I have a weighted undirected ...
0
votes
0answers
77 views

Shortest tour visiting given set of nodes in knight tour graph

Problem: Given knight tour graph $G$ ($8 \times 8$ nodes) and a set of nodes $\{ v_{1}, v_{2}, \dots, v_{n} \} = V \subset V(G)$, find a minimal length tour in $G$ that visits all nodes from $V$ (...
6
votes
1answer
410 views

How to extend Bellman-Ford to solve the $k$ shortest path routing?

Browsing the wikipedia I got to this page where it is said: Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one ...
3
votes
2answers
112 views

Shortest path between all pairs with colored nodes

I got a question from my homework in each I have the solution, but not the algorithm. I want to check if I understood it correctly. The question is: Let's say we have a directed graph with no ...
3
votes
2answers
207 views

Why doesn't Dijkstra's use a shortest-path first search?

When using BFS search on an unweighted graph to find the single-source shortest paths, no relaxation step is required because a breadth-first search guarantees that when we first make it to a node, we ...
0
votes
1answer
175 views

Why is my algorithm version so slow with this input?

Here I'm trying to do a comparison of two simple as possible algorithms, solving the symmetric travelling salesman problem, finding the optimal solution without the support of heuristics. I'm showing (...
1
vote
1answer
30 views

Dijkstra shortest path yields unintuitive results

Considering the following nodes with edge weights in red, Dijkstra's shortest path algorithm seems to return incorrect results, at least by the definition of the steps on wikipedia. By those rules, ...
1
vote
1answer
36 views

Dijikstra's algorithm with “hull” value catch

Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here. Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, ...
8
votes
1answer
387 views

How hard is finding the shortest path in a graph matching a given regular language?

Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some ...
4
votes
1answer
502 views

Shortest paths between given red vertices and arbitrary blue vertices

Given an undirected weighted graph, where each vertex has one of two colors - red or blue. I have to answer queries to find the shortest path between a given red vertex and any blue vertex in the ...
3
votes
0answers
100 views

Dynamic all pairs shortest path edge removal

I have a planar(|E|=O(V)) undirected graph with positive edge weights. I have already calculated all pairs shortest path with Floyd–Warshall algorithm. Now I want to recalculate APSP with an edge ...
4
votes
1answer
421 views

Dijkstra without decrease key

I was reading through this paper, "Priority Queues and Dijkstra's Algorithm" by Mo Chen et al., which suggests using Dijkstra's without edge relaxation, but to rather to just insert new ...
5
votes
1answer
1k views

Dijkstra with max instead of sum

Is it true that if we replace in the Dijkstra algorithm + with max, then the resulting algorithm correctly solves the problem of ...
1
vote
3answers
102 views

What's the best algorithm to find the shortest path between 2 vertices in a graph?

Considering an undirected and unweighted graph, what's the best algorithm to find the shortest path between two vertices?
0
votes
0answers
24 views

Decomposition of graph to subgraphs according to parallel edges

I am supposed to calculate all-pair shortest path lengths of a graph. However, I first need the graph to be decomposed/expanded to a simple one based on the presence of parallel edges. If N parallel ...
3
votes
1answer
131 views

Maximum value of arbitrage

I'm trying to solve this from The Algorithm Design Manual: 6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time ...
1
vote
1answer
169 views

Determine shortest path in a 4x5 grid graph

Suppose we had a graph $G = (V,E)$. This graph can also be seen as a $4x5$ grid graph as shown in the image. There is a directed edge from $v_{i,j} \rightarrow v_{i,j+1}$ for $1 \leq i \leq n$ and ...
2
votes
1answer
16 views

Performant algorithm to find edges without cross overs

I have a series of graphs with points plotted like this: Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don'...
4
votes
1answer
95 views

Optimal root in shortest path tree (SPT)

I would like to find the "optimal" shortest path tree (SPT) in some undirected weighted graph. As "optimal" SPT, I mean so its maximal path from root to leaf is minimal from any other potential SPTs. ...
2
votes
1answer
38 views

Proving inequalities related to Dijkstra's algorithm

Define $spdist(s,t)$ as the distance of the shortest path from vertex $s$ to $t$. Define $IN(v)$ as the set of in-neighbors of $v$. Define $w(u,v)$ as the weight of the edge $(u,v)$. I am asked to ...
1
vote
0answers
424 views

Remove a vertex from a graph keeping shortest path distance same

How could we delete an arbitrary vertex from a directed weighted graph without changing the shortest-path distance between any other pair of vertices? We are allowed to reweight the edges.
4
votes
1answer
68 views

Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
2
votes
2answers
373 views

How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph?

I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is ...
4
votes
1answer
614 views

Modifies Dijkstra’s Algorithm to find the maximum cost path

In a DAG and all weights are larger than 0. Is it possible to use a max heap to get the maximum cost?
1
vote
1answer
561 views

How does the slow All-pairs-shortest-paths algorithm work?

I am trying to fully understand the following algorithm from CLRS book: I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. ...
2
votes
0answers
23 views

Maintaining SCCs in directed graphs (on-line, under edge deletion) with ES-trees

I'm interested in efficiently maintaining the set of strongly connected components (SCC) in a directed (unweighted) graph under edge deletions only. While searching for ways I came across an article [...
-2
votes
2answers
94 views

Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?

I claim to have solved the travelling salesman problem as follows. (You will have to be familiar with djikstra's algorithm for this.) 1) I am about to start using djikstra's algorithm on any given ...
2
votes
1answer
168 views

Algorithm to find longest path in a tree that is smaller than x

Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any ...
1
vote
0answers
157 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. ...

1
2
3 4 5
12