-1
votes
0answers
19 views

k-maximally link disjoints paths with weight constraints

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
1
vote
1answer
57 views

Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?

I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths. An example is if we have ...
5
votes
2answers
152 views

Adding a node between two others, minimizing its maximum distance to any other node

We are given an undirected graph weighted with positive arc lengths and a distinguished edge $(a,b)$ in the graph. The problem is to replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a ...
1
vote
0answers
61 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 ...
0
votes
1answer
42 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
37 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
104 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 ...
1
vote
1answer
77 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 ...
0
votes
1answer
401 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
106 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 ...
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
87 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
217 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$ ...
2
votes
1answer
2k 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
1k 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
718 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, ...
2
votes
2answers
795 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.) ...
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
351 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
1answer
117 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?
1
vote
2answers
317 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 ...
2
votes
1answer
195 views

Shortest paths candidate

Let $G = (V,E)$ be a directed graph with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. ...
2
votes
1answer
808 views

Shortest path with exactly $k$ edges

From Skiena's book: Let $G = (V,E,w)$ be a directed weighted graph such that all the weights are positive. Let $v$ and $u$ be two vertices in $G$ and $k \leq |V|$ be an integer. Design an algorithm ...
5
votes
1answer
222 views

Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves

This problem is about finding a route on a square grid. The starting point is $(1,1)$ and the target point $(n,m)$. I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$. ...
3
votes
3answers
239 views

Find a vertex that is equidistant to a set of vertices?

I need help with the following problem: Input: An undirected, unweighted graph $G = (V,E)$ and a set of vertices $F \subseteq V$. Question: Find a vertex $v$ of $V$ such that the distance ...
5
votes
1answer
267 views

What is the maximum number of shortest paths between any pair of vertices in a chordal graph?

A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a ...
1
vote
1answer
88 views

Path on an edge-colored DAG using exactly $k$ colors

I have the following problem: Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$, does there exist a path from $s$ to $t$ using exactly $k$ ...
4
votes
2answers
215 views

Why not relax only edges in Q in Dijkstra's algorithm?

Can someone tell me why almost in every book/website/paper authors use the following: foreach vertex v in Adjacent(u) relax(u,v) when relaxing the edges, ...
7
votes
2answers
2k views

Finding negative cycles for cycle-canceling algorithm

I am implementing the cycle-canceling algorithm to find an optimal solution for the min-cost flow problem. By finding and removing negative cost cycles in the residual network, the total cost is ...
6
votes
1answer
1k views

Formalization of the shortest path algorithm to a linear program

I'm trying to understand a formalization of the shortest path algorithm to a linear programming problem: For a graph $G=(E,V)$, we defined $F(v)=\{e \in E \mid t(e)=v \}$ and $B(v)=\{ e \in E \mid ...
4
votes
1answer
1k views

Finding paths with smallest maximum edge weight

I need to find the easiest cost path between two vertices of a graph. Easiest here means the path with the smallest maximum-weigth edge. In the above graph, the easiest path from 1 to 2 is: ...
3
votes
3answers
4k 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? ...
7
votes
1answer
978 views

Dijkstra to favor solution with smallest number of edges if several paths have same weight

You can modify any graph $G$ so that Dijkstra's finds the solution with the minimal number of edges thusly: Multiply every edge weight with a number $a$, then add $1$ to the weight to penalize each ...
2
votes
1answer
2k views

Finding the Shortest path in undirected weighted graph

Is there an algorithm for finding the shortest path in an undirected weighted graph?
4
votes
4answers
5k views

Using Dijkstra's algorithm with negative edges?

Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance ...
6
votes
1answer
526 views

Bellman-Ford variation

I have a "smarter" version of Bellman-Ford here; this version is more clever about choosing the edges to relax. ...
11
votes
2answers
3k views

Shortest Path on an Undirected Graph?

So I thought this (though somewhat basic) question belonged here: Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving ...
13
votes
1answer
339 views

How many shortest distances change when adding an edge to a graph?

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in ...
7
votes
3answers
255 views

Unique path in a directed graph

I'm designing an algorithm for a class that will determine if a directed graph is unique with respect to a vertex $v$ such that for any $u \ne v$ there is at most one path from $v$ to $u$. I've ...