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

learn more… | top users | synonyms

1
vote
0answers
29 views

Shortest path with min-sum multiplication and Boltzmann distribution

My professor presented a method to find shortest paths using the min-sum multiplication and Boltzmann distribution. He multiplies the adjacency matrix many times and takes the $\beta$ of Boltzmann ...
1
vote
0answers
63 views

Finding shortest path from a node to any node of a particular type

I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is ...
-2
votes
1answer
15 views

why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm

We know Bellman Ford is an algorithm to find the negative cycle. And here is the algorithm for Bellman Ford Input: Given a graph G(V,E) and w(e) is weight Output: Return Yes if negative cycle exists. ...
1
vote
0answers
53 views

Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

Assumptions: given a graph with N nodes, and two specific nodes A and B the graph is undirected and no edge has a negative cost there exists at least one Hamiltonian path with A and B as an end ...
-1
votes
1answer
22 views

Is finding negative cycle vertices N-P complete?

Here is my question , I was trying to find the all the negative cycle vertices using bellman ford algorithm using this paper solution 7.1(b) in O(V) by tracing back the predecessor subgraph.It is also ...
4
votes
1answer
112 views

How to reduce the cost of search based on previous BFS?

I got an unweighted, undirected graph, with $N$ vertices, where each vertex has degree $K$. In my case its a grid with dynamic obstacles. My goal is to output a map, based on given location on the ...
1
vote
1answer
77 views

Shortest path from starting cell to all cells in the grid

I found an algorithm for finding the shortest path on grid between selected cell, to all cells on the grid, with $O(KN)$ where $K$ is the number of neighbor cells and $N$ is the number of cells. How ...
1
vote
1answer
45 views

Bellman-Ford without getting stopped by negative cycles

Let $s$ be the source vertex. In the standard Bellman-Ford algorithm (e.g. the version found in CLRS), when there is a negative cycle reachable form $s$, the algorithm will return that a negative ...
0
votes
1answer
50 views

Floyd–Warshall algorithm on undirected graph

I am referring to the algorithm from the Wikipedia page on the Floyd–Warshall algorithm. In case of undirected graphs should I change the assignment statement inside the ...
0
votes
1answer
41 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 ...
0
votes
0answers
32 views

Proof of shortest-paths optimality conditions

I am struggling with understanding the proof of shortest-paths optimality conditions. Let $G$ be an edge-weighted digraph. Then values in $distTo[]$ are the shortest path distances from $s$ iff: ...
3
votes
2answers
68 views

Shortest path in weighted(positive or negative) undirected graph

I have to find an algorithm that finds the SSSP (single-source shortest path - shortest paths from one source vertex to all other vertices) on a weighted undirected graph. If there are 2 different ...
4
votes
1answer
67 views

How to perform local search on simple paths?

I have a local search problem. The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph. The question is: given a current ...
0
votes
1answer
27 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 ...
1
vote
1answer
42 views

Using Dijkstra to find shortest path in relation to two weight functions?

I'm given a graph and two weight functions, $w_1$ and $w_2$, such that there doesn't exist a negative loop in the graph in $w_1$ and $w_2$. I'm also given two vertices, $s$ and $t$, and am asked to ...
1
vote
1answer
71 views

Shortest directed path connecting given subset of vertices

Given weighted directed graph $G = (V,E,w)$, where $w : E \to \mathbb R^+$ source vertex $v \in V$ vertex subset $U \subset V$ how to find a shortest directed path from $v$ containing all vertices ...
2
votes
2answers
180 views

Minimum path between two vertices passing through a given set exactly once

Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes ...
0
votes
0answers
94 views

Finding shortest path in a graph when edge weights depend on the chosen vertices

Here is my problem: I have a directed weighted graph with a substantial amount of vertices (few thousands), no cycles, in fact, it includes a starting node, a final node and an $m \times n$ grid ...
0
votes
1answer
179 views

Does “standard” Dijkstra's algorithm work with bi-directional edges and zero cost edges?

I have been reading about Dijkstra's algorithm and I think I understand it. I followed the algorithm in pseudo-code from Wikipedia, and now I wonder: If my graph is bi-directional and I add each ...
1
vote
2answers
92 views

Finding all paths with lengths in a fixed interval in sparse graphs

What is the most efficient way to find all paths of length M to N in a large sparse graph? Some general information: Graph has 30,000 to 50,000 nodes Average number of edges per node ~ 10 M=4, N=7 ...
2
votes
0answers
40 views

Update SSSPP solution on complete digraph on weight changes

I have a directed graph with $N$ vertices. Every pair of vertices is connected by two edges (one in each direction), and each of these edges has a weight which may be negative. On various occasions ...
13
votes
1answer
682 views

Why does Dijkstra's algorithm fail on a negative weighted graphs?

I know this is probably very basic, I just can't wrap my head around it. We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph. My ...
5
votes
1answer
342 views

Optimal algorithm to traverse all paths in the order of shortest path

I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path. The simplest way that comes to mind is to do a ...
2
votes
0answers
144 views

Any algorithm for finding Euclidean shortest path with specific constraints in 2D?

I have the following problem: In a 2D space with polygonal obstacles, find the shortest path between two given point. Without additional constraints, we can reduce it to a graph problem by ...
0
votes
1answer
366 views

How to optimize Dijkstra's algorithm for a grid graph?

I'm trying to apply Dijkstra's algorithm to the Problem 83 on projecteuler.net. The problem reads: In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by ...
2
votes
1answer
97 views

Non intersecting paths in a graph

I'm trying to come up with a good algorithm for the following decision problem: Let $G=(V,A)$ be a directed graph and let $s,t \in V$. Are there at-least 2 non-intersecting paths from $s$ to $t$? By ...
1
vote
2answers
322 views

Dijkstra's algorithm for edge weights in range 0, …, W

Suppose I want to run Dijkstra's algorithm on a graph whose edge weights are integers in the range 0, ..., W, where W is a relatively small number. How can I modify that algorithm so that it takes ...
0
votes
1answer
151 views

Find least probable path in graph

I am working on a special case of the longest path problem. For a cyclic directed graph $G=(V, E)$, where the edge-weights are probability values (i.e., $P(\_) = w(s, q)$ with $s,q \in V$), my aim is ...
1
vote
0answers
68 views

k-shortest paths

Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the ...
2
votes
2answers
1k 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 ...
4
votes
2answers
92 views

Path finding under constraints

Let $ G=(V,E) $ be a directed graph with a real weight function $w$ defined on the edges and $ a,b \in V$. Let $\alpha$ denote the minimal weight of all paths from $a$ to $b$ and $\beta$ denote the ...
1
vote
1answer
96 views

Can Floyd-Warshall be used to solve an APSP problem without copying the matrix?

According to CLRS, each iteration of the outermost loop (on $k$) makes a new copy of the adjacency matrix. Is it safe not to copy the matrix on every iteration? What I mean is, according to CLRS: ...
4
votes
2answers
78 views

Uniformly random efficient sampling of shortest s-t paths, with optimal random bits

Motivated by Efficiently sampling shortest s-t paths uniformly and independently at random, The answers give methods of randomly sampling shortest $s\text{-}t$ paths. However, they use a lot of ...
3
votes
0answers
86 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 ...
11
votes
2answers
206 views

Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random

Let $G$ be a graph, and let $s$ and $t$ be two vertices of $G$. Can we efficiently sample a shortest $s$-$t$ path uniformly and independently at random from the set of all shortest paths between $s$ ...
11
votes
2answers
734 views

Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)? For ...
2
votes
1answer
1k views

A* to find the longest path in a directed cyclic graph

I have written an A* algorithm to find the shortest path through a directed cyclic graph. I am trying to modify it to find the longest path through the same graph. My attempt was to write it so that ...
1
vote
2answers
988 views

Shortest path that passes through specific node(s)

I am trying to find an efficient solution to my problem. Let's assume that I have positive weighted graph G containing 100 nodes(each node is numbered) and it is an ...
3
votes
1answer
661 views

Running Floyd-Warshall algorithm on graph with negative cost cycle

I am trying to find the answer to the following question for the Floyd-Warshall algorithm. Suppose Floyd-Warshall algorithm is run on a directed graph G in which every edge's length is either -1, 0, ...
3
votes
1answer
157 views

An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

Is there an incremental directed graph data structure that has the following properties: Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper ...
2
votes
2answers
769 views

Shortest Minimax Path via Floyd-Warshall

I am trying to modify the Floyd-Warshall algorithm to find all-pairs minimax paths in a graph. (That is, the shortest length paths such that the maximum edge weight along a path is minimized.) ...
6
votes
1answer
140 views

Approximability of the edge-disjoint shortest paths problem

In the edge-disjoint paths problem (EDP), we are given a (possibly directed) graph $G=(V,E)$, and a set of distinct source-sink pairs $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$, and we want to maximize ...
2
votes
1answer
157 views

Finding path with minimum weight

There is a river which can be considered as an infinitely long straight line with width W. There are A piles on the river, and B types of wooden disks are available. The location of the $i$-th pile ...
2
votes
1answer
324 views

Can the shortest simple cycle between two given nodes be found in polynomial time?

Given an undirected simple graph $G$ and two nodes $s$ and $t$, the question asks for an algorithm to find the shortest simple cycle (no edge or vertex reuse) that contains the two. As far as I know, ...
2
votes
0answers
262 views

Route planning in public transport application

This is a cross-post of this StackOverflow question, (I'm not aware of linking questions between StackExchange sites). You can ignore the part about programming. I'm making a journey planner (or a ...
2
votes
0answers
57 views

Multicommodity shortest path problem on a directed acyclic graph

I have n commodities with each a unique source and sink node. Each source-sink pair is connected in some manner on a directed acyclic graph. All arc weights are non-negative. The goal is to find the ...
1
vote
1answer
60 views

For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?

Apparently, if we use Djikstra's algorithm to find the shortest path between the root node and all other nodes in a weighted graph with no negative cycles, we are done after updating the distance of ...
-2
votes
1answer
115 views

Find the weight of the lightest path from u to v

Find the weight of the lightest path from u to v the goes through node a or/and b. Do you have a suggestion on how it can be done?
3
votes
2answers
113 views

Finding all vertices on negative cycles

Given a weighted digraph, I can check whether a given vertex belongs to a negative cycle in $O(|V|\cdot|E|)$ using Bellman-Ford. But what if I need to find all vertices on negative cycles? Is there a ...
1
vote
2answers
311 views

Shortest path with odd weight

Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd. We are looking for an algorithm for finding the weight of the shortest odd ...