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
1answer
1k views

Betweenness centrality measurement ignoring inverse paths?

I'm implementing the Betweenness Centrality algorithm proposed by Brandes (first algorithm on this paper - also below), and I'm running into a very weird issue: it seems to be ignoring some paths (i.e....
0
votes
1answer
1k views

Use Dijkstra to find negative cycles in a graph [closed]

I will state the problem: Suggest an algorithm that works in $O(|E| + |V|log|V|)$ time that checks if there are negative cycles in a graph. So, I saw the runtime, and I immediately said we need to ...
0
votes
1answer
34 views

Create Shortest Path tree for every node after Floyd Warshall in O(nm)

Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after ...
0
votes
1answer
39 views

Shortest Path with a twist

We are given a Graph G where, s ∈ V and t ∈ V. w:E such that w represents the time from u to v. We have to calculate shortest path between s to t with a twist. The twist is the turbocharger which can ...
0
votes
1answer
93 views

Clarification in the proof for the Bellamn-Ford algorithm

While proving the correctness of the Bellman-Ford algorithm, we prove the following lemma: After k (k >= 0) iterations of relaxations, for any node u that has at least one path from s (the start ...
0
votes
1answer
143 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
166 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
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 ...
0
votes
1answer
111 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 ...
0
votes
1answer
27 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 ...
0
votes
1answer
241 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 ...
0
votes
1answer
80 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, ...
0
votes
1answer
169 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 ...
0
votes
1answer
116 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 ...
0
votes
1answer
436 views

Consistent heuristic and A*

The following graph has consistent heuristic. An A* algorithm will alter its first guess ACD to the correct shortest path ABD... if it has consistent heuristic, doesnt it mean, that AB should be ...
0
votes
1answer
640 views

Dijkstra's shortest path algorithm without relaxation

Although I have found a very similar question to what I want to ask here (https://codereview.stackexchange.com/questions/96064/dijkstras-algorithm-without-relaxation), yet I didn't find a satisfactory ...
0
votes
1answer
41 views

How to prove that a custom iterative algorithm will determine all shortest paths to a graph node?

I'm not sure what the following algorithm does but it seems that it calculates the shortest paths from a node $t$. Initially we're given a graph $G=(V,E)$ with non-negative weights $c(e) \ge0$ for ...
0
votes
1answer
384 views

How to tell if a spanning tree is a shortest-spanning tree of a DAG?

I know how to calculate the shortest paths from source s to all other reachable vertices in a DAG (with no negative weight on the edges) By iterating the ...
0
votes
1answer
108 views

Confirmation of Dijsktra application explanation

Please can someone confirm that my description of the application of Dijkstra's algorithm is correct for this graph? ...
0
votes
1answer
587 views

Shortest distance from a set of points

Consider an unweighted, undirected, simple graph $G=(V,E)$. We have some subset $S \subseteq V$, and we want to determine the shortest distance from any vertex $v\in V$ to some vertex $s\in S$. To ...
0
votes
1answer
1k views

Brandes' betweenness algorithm for weighted undirected graph

I am studying Brandes' betweenness algorithm for weighted undirected graph. I am not sure that, in Algorithm 1 (which is based on Dijkstra's shortest path algorithm), If a node is first encountered, ...
0
votes
1answer
3k views

Best pathfinding algorithm for undirected unweighted graph [closed]

I have an unweighted undirected graph with every node connected with an average of two hundred other nodes (nodes are people from social network). What will be the fastest algorithm to find the ...
0
votes
1answer
169 views

Application of shortest vertex-disjoint path with time window

I am working on finding shortest disjoint path problem, When there are distinct origin destination pairs and there is a predefined time window (or length) associated with each object (which we want to ...
0
votes
1answer
519 views

Modified Bellman Ford to find minmum cost cycle in O(E²V) time?

I'm thinking about how you can modify Bellman Ford a bit to calculate the minimum weight cycle in an undirected graph with positive weights. Note that the constraint is that the algorithm must run in $...
0
votes
1answer
2k views

Dijkstra single-source shortest path $\Omega(n\log n)$?

If I have a directed graph with $n$ weighted edges, is it possible to prove that Dijkstra's single-source shortest path algorithm takes $\Omega(n\log n)$ in the worst case? I know heaps reduce ...
0
votes
1answer
294 views

Single Source Shortest Path: What does the weights on the vertex and edges tell you?

In MIT's open courseware (http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf), I do not see how computing a set of numbers on the edge and the vertex will produce the shortest path. Can ...
0
votes
1answer
334 views

Find longest path between two disjoint sub-sets of vertices $V_1, V_2 \subset V$ of a Graph

I have a homework question which I would appreciate some help with: Let there be a DAG $G=(V,E)$ with positive weights. For every two different vertices $v_1, v_2$ we will define $D(v_1, v_2)$ to be ...
0
votes
1answer
147 views

shortest time based on traffic congestion data [closed]

I want to develop one algorithm which can predict shortest time to be taken to go to a destination from a source in a road network based on traffic congestion data. Consider that I have a server ...
0
votes
1answer
12 views

Finding shortest path for DAG using dynamic programming vs topological sort?

Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the ...
0
votes
0answers
39 views

Most popular path in weighted cylic directed graph

Context I have a graph $G=(V,E)$ with weighted edges, all weights are positive integers $w(e)\in\mathbb{N}\setminus\{0\}$. The weights represent the popularity/count of each edge, for example $w(e) = ...
0
votes
0answers
13 views

What's the best way to combine multiple A* searches?

I have a graph that looks like this The highlights nodes must be visited, and the blue node must be visited last, the stickman must be the start of the path. The weights are the Euclidean distance ...
0
votes
1answer
60 views

Using A* path finding is giving me inaccurate results

So i am using A* path finding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of ...
0
votes
0answers
33 views

The shortest path that visits every specified node before finally reaching the specified end node?

After asking another question(Is the last step in the Christofides' algorithm necessary), I have decided Christofide's algorithm probably doesn't solve the problem I'm facing. Is there any ...
0
votes
0answers
19 views

What is the significance of Bellman-Ford and linear programming for scheduling and makespans?

CLRS exercise 24.4-9 says the following: Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity $\max_i\{x_i\...
0
votes
1answer
23 views

Vertices reachable from negative-weight cycles in Bellman-Ford

TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-...
0
votes
0answers
15 views

Min-plus matrix and Shortest path variation

I was solving a problem in which given a directed weighted graph with no self loops (adjacency matrix),I had to find minimum path of length at least K between ever pair of nodes. One method is : let ...
0
votes
0answers
13 views

Genetic algorithm with a visited path list

I am currently working through the Computational Intelligence: An Introductionbook by Andries Engelbrecht. I forked a simple implementation of a genetic algorithm trying to solve a path planning ...
0
votes
0answers
21 views

Parallel Floyd-Warshall algorithm in Assembler - possible?

I want to implement parallel Floyd-Warshall algorithm in assembler. The FW algorithm is all about if and assign statements ...
0
votes
0answers
42 views

Bellman-Ford algorithm from Éva Tardos

I am trying to understand the Bellman-Ford algorithm from Jon Kleinberg, Éva Tardos: *[Algorithm Design]. Page no: 296 The recursive equation that is written: $$M[v]= \min(M[v], \min_{w\in V} (c_{vw} +...
0
votes
0answers
37 views

Solving shortest path problem with Dijkstra’s algorithm for n negative-weight edges and no negative-weight cycle

Although many texts state Dijkstra's algorithm does not work for negative-weight edges, the modification of Dijkstra's algorithm can. Here is the algorithm to solve a single negative-weight edge ...
0
votes
1answer
341 views

Why is DFS not suited for shortest path problem?

I am sorry for the repetition of the question. I understand that this question has already been answered before by the community, but most answers tend to focus on unweighted graphs. I want to know ...
0
votes
1answer
775 views

Google Foobar Level 4 - Graph Problem

So, I have been solving problems in Google Foobar for the past two weeks or so ans has reached Level 4. The first problem is as stated below and I have come up with a solution which is able to pass ...
0
votes
0answers
152 views

Removing any arbitrary vertex from a directed graph?

I came upon this particular question which I do not understand from Jeff E. Algorithms, Chapter 9, ex. 8. https://jeffe.cs.illinois.edu/teaching/algorithms/book/09-apsp.pdf How can we remove any ...
0
votes
0answers
19 views

Dinamic programming relationships in the all-pairs shortest paths problem

CLRS includes two dynamic programming algorithms for solving the same problem: all-pairs shortest paths. The kernels of these algorithms (side-by-side) look almost identical, except that they seem to ...
0
votes
1answer
105 views

MIT 6006 Quiz 2: The shortest path task

I'm looking for some clarifications on an algorithmic task I've been trying to solve. This task is a part of Quiz 2 from the MIT 6.006 course. The main idea of creating ...
0
votes
0answers
34 views

Algorithm to calculate shortest path when updating the heaviest edge in a path [duplicate]

For a given graph $G=(V,E)$ and path $p= v_1 \to v_2 \to ...\to v_k$, $w^\ast(p)$ represents the weight of the path between $v_1$ and $v_k$ excluding max_edge. $$w^\ast(p) = \sum_{i=1}^{k-1} w(v_i, v_{...
0
votes
0answers
29 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 ...
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 ...
0
votes
0answers
54 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 ...
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$ (...

1
8 9
10
11 12