The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [shortest-path]

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

464 questions
Filter by
Sorted by
Tagged with
490 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} \...
1k 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 ...
3k views

### Bellman-Ford and zero-distance cycle

Problem statement: Given a graph G(V,E) which is not acyclic and may have negative edge weights (and thus may possibly have negative-length cycles), how does one detect if the graph has a zero-length ...
29 views

### Longest simple walk below a certain weight

Given a directed graph G and a starting vertex $v$ and a cutoff weight $w$, I want to find a simple walk with net weight < $w$ that visits as many nodes as possible. Currently, I have a recursive ...
138 views

### Intersection of two shortest paths in connected weighted graph

Let $G=(V,E)$ be a connected directed weighted graph with non-negative weights on edges. Let $u,v,s,t$ be vertices in the graph $G$. I need to find an algorithm which in $O(|E|\log |V|)$ time checks ...
31 views

### When talking about the length of a path in a graph, what exactly is a skip?

I'm studying for a final and when looking for the shortest path in a graph from one vertex to another, what is meant by k-skips? One website defines it as the ability to change the weight of one edge ...
135 views

### Early termination of A* with weak heuristic if solution is known

I have a large graph G and a pair of nodes s,t. I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent. Suppose I already know of a path ...
505 views

### Shortest Path Variant (constrained max hop)

INPUT: directed non negative weighted graph, s, t, k OUTPUT: SSSP from s to t where the path has $\leq k$ vertices MY PROGRESS: ...
392 views

### All Pairs Shortest Path Fewest Stops

I have a graph with V vertices and E edges. Each edge is a road that takes fuel F to travel. I have a gas tank of capacity K, and want to find the fewest number of refills needed to go from any vertex ...
560 views

### Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...
7k views

### Destination-based vs source-based routing

I understand that destination-based routing builds the "route" from the destination backwards to the source (e.g. if using a spanning tree, then the tree is routed at the destination). With source-...
110 views

### How to minimize the sum of edge weight in the graph while keep the all-pair shortest path greater than a constant?

For example, if we have a graph G = (V, E) and a subset of vertices $U \subset V$. We can set $w(e)$ where $e \in E$ to be a non-negative real number. We want to minimize the total edge weight, but ...
41 views

### Defining preferred paths makes $A^*$ heuristic lose admissibility

In a geographical graph, where each edge's cost is equal to the physical distance between its nodes, one can be tempted to manipulate the cost of some of the edges, to make it a bit lower, in order to ...
79 views

### Shortest paths in isomorphic graphs with different edge weights

I'm looking for a way to find the shortest paths from a source to all destinations in isomorphic undirected graphs with different edge weights. The only thing I can think of is using Dijkstra on each ...
405 views

963 views

### How to find all shortest paths between two nodes in a weighted undirected graph? [closed]

How to find all shortest paths between node 1 and N in a weighted undirected graph? There can be multiple edges between two nodes. I want to find all nodes that can be on a shortest path. For example:...
170 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 ...
2k 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) ...
2k 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 ...