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

learn more… | top users | synonyms

0
votes
0answers
23 views

Widest Path Algorithm [on hold]

I am planing to change dijkstra algorithm from shortest to widest path, so can any one help me to change the algorithm? just tell me the widest path algorithm then I will do practically thanks.
-1
votes
1answer
39 views

Algortihm for path existence in a N by N board moving with a chess knight

I have a problem which goes like this. There is an $N$ x $N$ board in which some squares are maked with $x$. The upper left and lower right corner squares are also marked. You have a chess knight ...
2
votes
1answer
77 views

Do we want largest or smallest priority in the A* algorithm?

On this site http://algs4.cs.princeton.edu/25applications/ is described A* algothihm this way The A* algorithm is a problem-solving process where we put the start configuration on the priority ...
0
votes
1answer
38 views

Comparison between IDA* and Recursive best first search

How does IDA* compare to recursive best first search (RBFS), in terms of (a) the number of nodes expanded, and (b) space complexity? Both algorithms are intended to be memory-efficient heuristic ...
2
votes
2answers
93 views

Delivery Algorithm - Find shortest paths

Given - A center(lat=x,lng=y) 'C' from which a delivery boy makes a round trip. A delivery boy has a bag which may contain at the most 10 boxes to deliver. A set of points Di (lat=xi,lng=yi) ...
2
votes
0answers
59 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping ...
4
votes
1answer
76 views

What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms

I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms: When the same heuristic ...
0
votes
2answers
46 views

Existence of shortest path in a graph with no negative cycles?

Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex. How do I prove that for every ...
1
vote
1answer
48 views

Shortest Path problem(Single Source&Destination) [closed]

Given: A completely connected directed acyclic graph. What would be the most efficient(Least Time complexity) way to find a shortest path among a very large number of nodes? Constraint: 1)The result ...
2
votes
2answers
157 views

Find all the paths from node A to node B

You are given a bunch of nodes evenly spaced in a rectangular grid. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand (northwest) corner and node B is at the bottom ...
1
vote
1answer
86 views

Computing the k shortest edge-disjoint paths on a weighted graph

Looking for k shortest paths that do not share edges. i.e if the paths were represented as sets of edges, their intersection has to be empty. We could use Dijkstra to find the 1st "disjoint" (edge ...
3
votes
0answers
38 views

Finding partial traveling salesman path of specified length

For a given set of nodes, I can find optimal paths that visit all nodes using various traveling salesman algorithms. As a subset of this problem, I would like to be able to find shortest partial ...
3
votes
1answer
388 views

Algorithm to find all paths of length k

Consider the following definition of 3-friends: person 1 is 3-friends with person 2 if they are direct friends or person 1 is friends with a friend of person 2 or person 1 is friends with a friend ...
1
vote
0answers
18 views

How do I apply a single iteration of Floyd's algorithm to an adjacency matrix? [closed]

I have the following adjacency matrix for a graph with nodes {a,b,c,d}: \begin{bmatrix} & & a& b& c& d\\ & & & & & \\ a& & 0& ...
-1
votes
1answer
50 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 ...
2
votes
1answer
84 views

Why can't edit distance be solved as L1 distance?

Given two strings $x$ and $y$ over the alphabet $\Sigma$ one defines the edit-distance $\text{ed}(x,y)$ as the minimum number of substitutions, insertions and deletions of characters required to ...
0
votes
0answers
15 views

Finding next lightest path [duplicate]

Using Dijkstra algorithm, how can I find the next shortest path in a directed weighted graph? (When saying next, I mean that the next path must be heavier than the lightest path and not equal). The ...
0
votes
0answers
18 views

A way to order a shortest path tree

Given the shortest path tree of a directed graph G=(V,E) and w: E-> R , source vertex s and an assumption that there are no negative cycles in the graph. In the homework assignment we need to find ...
0
votes
1answer
43 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 ...
1
vote
0answers
78 views

Weighted, Acyclic Graph and Change Weights Problem?

I ran into a question as follows: We have a Code on Weighted, Acyclic Graph G(V, E) with positive and negative edges. we change the weight of this graph with ...
3
votes
1answer
89 views

Shortest paths in weighted graphs, and minimum spanning trees

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
1
vote
0answers
38 views

Fully dynamic k-shortest-path

Problem: My graph is a directed acyclic graph with positive edge weights. It is constantly changing in that nodes are deleted and added. For each change, I need to find the k-shortest-path. My ...
4
votes
1answer
132 views

Bellman-Ford Termination when there is no change on vertex weights?

We know the bellman-ford algorithms check all edges in each step, and for each edge if, d(v)>d(u)+w(u,v) then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the ...
0
votes
1answer
86 views

Shortest path in a matrix

I am trying to solve this problem, and i have tried multiple methods, but i must be missing something, here is the problem: Given a matrix MxN. Find the shortest path from (1,1) to (M,N), where each ...
1
vote
0answers
47 views

How to convert a search solution to a path to be tracked?

Let's say I have a space with obstacles and I'm trying to control a robot's movement while avoiding obstacles. I also have a start state and a goal state. I use a search algorithm to find the shortest ...
3
votes
1answer
96 views

Shortest path in a mutable graph

I have an acyclic edge-weighted graph and have used Dijkstra's Algorithm with topological sort to find any shortest path to every other node from a root $s$. This is performed in time proportional to ...
3
votes
2answers
78 views

Finding the lightest simple path in trees with integer weights

A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest ...
4
votes
0answers
190 views

Suurballe's Algorithm: Proof of Correctness

I was reading about Suurballe's algorithm on Wikipedia, for the shortest edge-disjoint paths problem, i.e. given nodes $s$ and $t$ finding a pair of paths between these nodes, whose accumulated weight ...
3
votes
2answers
1k views

Is there an algorithm to find all the shortest paths between two nodes?

Given a directed graph, Dijkstra or Bellman-Ford can tell you the shortest path between two nodes. What if there are two (or n) paths that are shortest, is there an algorithm that will tell you all ...
0
votes
2answers
78 views

Shortest path where weights are computationally expensive to calculate

Suppose we have a function, CalculateEdgeWeight, which is computationally expensive. We want to find the shortest path between two nodes $s$ and $t$ in a simple edge-weighted digraph $G= (V,E)$ where ...
1
vote
1answer
224 views

Algorithm to find shortest path between two nodes

I want an algorithm similar to Dijkstra or Bellman-Ford for finding the shortest path between two nodes in a directed graph, but with an additional constraint. The additional constraint is that ...
3
votes
1answer
143 views

Linear programming formulation of cheapest k-edge path between two nodes

Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges. Here is my attempt using a flow network: \begin{align} ...
1
vote
1answer
95 views

Shortest walk that covers $k$ nodes

I have the following problem, I would like to know an efficient algorithm to solve it. Suppose I have a weighted graph $G$ and a set of vertices $K$, I want to find a walk which starts at a vertex ...
1
vote
1answer
127 views

kth nearest vertex in a unweighted graph

Given an unweighted undirected graph $G$ with $10^5$ vertices and a subset $S$ of special vertices and an integer $k$, I want to find the $k$th nearest special vertex for each vertex. What algorithm ...
0
votes
1answer
38 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 ...
4
votes
2answers
113 views

Algorithms: Difference Constraints

I'm currently studying for my algorithms final and I came across a practice problem that I can't seem to figure out. Here's the problem: Consider the following set of difference constraints: ...
0
votes
0answers
16 views

Can negative weight cycle problem be resolved if we were to add a constant to all weights? [duplicate]

Suppose a graph contains three nodes a, b, c where w(a,b) = 5, w(b,c) = -4, w(c,a) = -6. Now let's add a 6 to all weights, so we have w(a,b) = 11, w(b,c) = 2, w(c,a) = 0. This seems to eliminate ...
1
vote
1answer
67 views

Transforming the sorting problem into Dijkstra [closed]

To get a lower bound of nlogn I am taking the sorting algorithm, which is well known to have that, and transforming/adapting it to Dijkstra's single source shortest path problem. I know you need to ...
0
votes
1answer
125 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
2answers
90 views

Bellman–Ford negative path meaning

In the Bellman–Ford algorithm, what is the practical meaning of having a negative path between routers? I have tried searching the net but didn't find any data thanks Eli
5
votes
2answers
443 views

Is Dijkstras algorithm used in modern route-finding systems?

Is Dijkstra's algorithm used in modern route-finding systems such as Google maps or the satnav in your car? If not, then what is?
1
vote
1answer
252 views

find the shortest path between two nodes where the number of edges is minimal [closed]

Say you are given an undirected unweighted graph, where s and t are nodes from the graph. d(s,t) means the distance between s and t which outputs the number of edges. How do I find the the maximum ...
5
votes
0answers
74 views

Are there Some Pairs Shortest Paths Algorithms?

I know that there are All Pairs Shortest Paths algorithms. But I am not sure if they are effective if I am trying to solve the Pairs-Shortest-Path problem for a subset of my vertexes. The properties ...
2
votes
2answers
272 views

Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph

I'm learning Dynamic Programming (By myself) and in the textbook there is this question: Given two undirected graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ over the same set of Vertices $V$ and a weight ...
0
votes
1answer
56 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. ...
5
votes
1answer
193 views

Proof of Dijkstra Algorithm Optimality

Has it been proven that Dijkstra's algorithm is optimal for asymptotic worst case of single-source shortest path on directed graphs? (Assume no preprocessing) I became curious when Wikipedia ...
0
votes
0answers
70 views

A* cost implications of arbitrary/dynamic point on edge in navmesh

I currently have a working implementation of A* using navigation meshes. Agents are moving around a 3d navigation mesh, reaching their target, however often a sub-optimal path is chosen, when ...
2
votes
2answers
196 views

Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?

Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$. ...
2
votes
1answer
155 views

Dijkstra's Algorithm with different color nodes

You are given a directed graph G = (V, E) and nodes s, t. Nodes are colored red, white, and blue. A path from s to t is called colorful if it contains both a red node and a blue node. The task is to ...
1
vote
1answer
57 views

Minimizing total distance to a point from a set of points

I've read about a problem: There are $n$ houses that are placed randomly. Place a parking lot so that the (straight-line) distance to all houses is minimal. I've written a Monte-Carlo algorithm, ...