Given an acyclic, directed, and weighted graph.

Now how can I determine how many shortest paths are there from source to destination, if i use Dijkstra’s algorithm?

# Tag: Shortest

## 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 without negative-weight edges.

Let $d_s(v)$ be the shortest distance from source vertex s to vertex v.

Suppose the negative edge $e$ is $(u, v)$

First, remove the negative edge $e$, and run Dijkstra from the source vertex s.

Then, check if $d_s(u) + w(u, v) leq d_s(v)$. If not, we are done. If yes, then run Dijkstra from $v$, with the negative edge still removed.

Then, $forall t in V $, $d(t) = min(d_s(t), d_s(u) + w(u, v) + d_v(t))$

Given the above algorithm, I want to modify the above algorithm again to solve n negative-weight edges and no negative weight cycle. Any hint?

## weighted graphs – 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 **Can DFS we used to find the shortest path for weighted graphs?** I know that Dijkstra’s algorithm is used to find the shortest path for weighted graphs. **But, what I want to know is what is fundamentally different in using DFS for unweighted graphs compared to Dijkstra (which is BFS + priority queue/set) and why can’t we create DFS + priority queue/set implementation for shortest path problem?**

Ref link: Shortest Path using DFS on weighted graphs,

Why can’t DFS be used to find shortest paths in unweighted graphs?

Any help would be really appreciated.

Thanks!

## algorithms – Shortest Path in a Directed Acyclic Graph with two types of costs

I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). The edges in G have two types of costs – a nominal cost $w(e)$ and a spiked cost $p(e)$.

The goal is to find a path from a node $s$ to a node $t$ that minimizes the following cost: $$sum_e w(e) + max_e {p(e)},$$ where the sum and maximum are taken over all edges of the path.

Standard dynamic programming methods show that this problem is solvable in $O(E^2)$ time. Is there a more efficient way to solve it? Ideally, an $O(Ecdot operatorname{polylog}(E,V))$ algorithm would be nice.

## shortest path algorithm – why backtrack from the end node instead of starting from the starting node?

You want to find the shortest paths $S(s,v)$ to **all** nodes $v$ (31:30 in the video). In other words, we are interested in computing a function $f(v) = S(s,v)$, and, as explained in lecture, you can write it as $f(v) = min_{(u,v) in E} f(u) + w(u,v)$. In the end, it allows you to compute all such values in one go.

If you instead consider an equation $S(s,v) = min_{(s,u) in E} w(s,u) + S(u,v)$, you do can find $S(s,v)$ this way. However, you won’t be able to find $S(s,u)$ for all other $u$ in the process, and you’ll have to run the same algorithm again for other end vertices.

## Graph search or shortest path algorithm for graph with multiple “goals”?

I did a project in a class using A* search to solve an 8-puzzle.

But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles.

I’m not sure whether something like A* search could still work or not. I have trouble fathoming how a heuristic might be designed.

Are their other shortest path algorithms or search algorithms that are better suited for this kind of problem?

## shortest path – Bellman Ford Dynamic Programming

Dynamic programming doesn’t necessarily mean that your solution will be efficient. It just means that your problem can be defined using a recursive function, for which you can use memoization.

To understand what this function is, take a look at the proof. The invariant is “after $i$ iterations, we’ve found all shortest paths of length at most $i$“. Therefore, we can define our function $f(v, ell)$ – the length of the shortest path to vertex $v$ with length at most $ell$ – in the following way:

$$f(v, ell) = min_{u in in(v)} (f(u, ell-1) + d(u,v))$$

What Bellman-Ford does is slightly different (e.g. it can compute all shortest paths in a single iteration, if our order is lucky), but it can only help us, so we don’t mind.

## shortest path – 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 arbitrary vertex from a directed graph, with weighted edges that can be positive negative or zero, without changing the shortest paths distance between all other pairs of vertices, in $O(V^2)$.

Let $G=(V,E)$ be a directed graph with weighted edges; edge weights could be positive, negative, or zero.

a) How would we delete an arbitrary vertex $v$ from this graph, without changing the shortest-path distance between any other pair of vertices? Describe an algorithm that constructs a directed graph $G’=(Vsetminus{v},E’)$ with weighted edges, such that the shortest-path distance between any two vertices in $G’$ is equal to the shortest-path distance between the same two vertices in $G$, in $O(V2)$ time.

I have an idea would be to just consider the incoming edges $u rightarrow v$ and outgoing edges $v rightarrow t$ and for each $u$, add an edge $u rightarrow t$ with the weight being the sum of the weights of $u rightarrow v$ and $v rightarrow t$, for all $t$. The second part builds upon the first, but now I am confused about how to go about it.

Now suppose we have already computed all shortest-path distances in $G’$.Describe an algorithm to compute the shortest-path distances in the original graph G from v to every other vertex, and from every othervertex tov, all in $O(V^2)$ time

Is there a way to do this now that I have deleted the node?

## graphs and networks – How to choose the shortest route?

Someone needs to start from home and complete the three tasks of going to the post office to send a letter, going to the bookstore to buy books, and going to the supermarket to buy food. He can walk through some nodes repeatedly. How should he choose the route to make the path the shortest?

```
Graph[{Home [UndirectedEdge] School,
Home [UndirectedEdge] Supermarket,
Home [UndirectedEdge] PostOffice,
PostOffice [UndirectedEdge] Home,
PostOffice [UndirectedEdge] Bookstore,
PostOffice [UndirectedEdge] Supermarket,
Bookstore [UndirectedEdge] PostOffice,
Bookstore [UndirectedEdge] Supermarket,
Supermarket [UndirectedEdge] Bookstore,
Supermarket [UndirectedEdge] PostOffice,
Supermarket [UndirectedEdge] Home,
Supermarket [UndirectedEdge] School,
School [UndirectedEdge] Supermarket,
School [UndirectedEdge] Home},
EdgeWeight -> {410, 510, 218, 218, 75, 329, 75, 440, 440, 329, 510,
125, 125, 410}, VertexLabels -> "Name",
VertexCoordinates -> {Home -> {0, 0}, School -> {1, 0},
PostOffice -> {0.2, 1}, Supermarket -> {1.2, 0.8},
Bookstore -> {0.4, 1.7}}]
```

If possible, I hope the respondents can provide as many methods as possible to solve this problem, such as neural network algorithm, genetic algorithm, or built-in function solution, etc.

## algorithm – A system that figure out the fastest (not shortest) navigation method between points for 2D spaceship with 2 axes propulsion

I am working on a space themed game with space being a 2D pane. The player issue order by clicking on the coordinate for his/her ship to navigate to a certain point on the pane.

The player ship can:

- Propel forward and backward
- Strafe starboard and port
- Yaw starboard and port

The ship’s performance on each direction varies greatly depending on configuration. Some may move faster on sides and back directions than they do forward direction.

I have combined A* and PID control for navigation but couldn’t help but noticed that in many occasions where the ship could have accelerate to the full speed and turn towards the target to reach the target faster, it instead turns in place while strafing slowly until it faces the destination before accelerating.

I would like to add another calculation that let the ship knows which navigation approach it should take to minimize the time to reach the target but I have no idea which field of study I should look into or if there is a quick win scenario I could use to achieve an expected outcome.

Please kindly recommend and thank you very much in advance.