## 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?

Posted on Categories proxies

## find shortest paths from source to all vertices using Dijkstra’s Algorithm?

For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph but how can i calling the algorithm |V| times taking each vertex as a source and store all tables ??? For example : What is the shortest path from 1 to 4? You need to print the value and the exact path vertices starting from 1 and ending at 4.

Posted on Categories proxies

## Good test cases to catch bugs in my dijkstra’s implementation?

What are some good test cases that can help me debug my implementation of dijkstra’s algorithm? I am not looking for negative edge weight graphs.

Posted on Categories proxies

## “Subpaths” of Dijkstra’s shortest path also shortest?

I have trouble putting this into formal mathematical terms, so let’s suppose that I found the shortest path from A to E as A > C > D > B > F > E with Dijkstra’s algorithm. Am I correct in assuming that the shortest path from C to B would be C > D > B, and that the shortest path from D to F would be D > B > F?

Posted on Categories proxies

## Why doesn’t Dijkstra’s use a shortest-path first search?

When using BFS search on an unweighted graph to find the single-source shortest paths, no relaxation step is required because a breadth-first search guarantees that when we first make it to a node, we have found the shortest path to it.

However, Dijkstra has no such guarantee, because the neighbours of each node are checked in no specific order. Therefore, we need a relaxation step to update the shortest path of each node if we later find a shorter path.

Instead of choosing a random neighbour, why not always follow the neighbour with the shortest path? I think that would guarantee we have always found the shortest path and no relaxation step is required. I implemented this in Python and it seems to work. Am I missing something?

from heapq import heappop, heappush  def shortest_path_lengths(graph, source):     dist = {}     q = [(0, source)]     while q:         cur_dist, v1 = heappop(q)         if v1 in dist:             continue         dist[v1] = cur_dist         for v2, v1_to_v2_dist in graph[v1].items():             if v2 not in dist:  # check it hasn't been visited already                 heappush(q, (cur_dist + v1_to_v2_dist, v2))     return dist   graph = {     'a': {'b': 3, 'c': 5},     'b': {'c': 1},     'c': {'d': 4},     'd': {}, } print(shortest_path_lengths(graph, 'a')) 
Posted on Categories proxies

## How Dijkstra’s algorithm forms shortest path tree when multiple nodes have same shortest path length

I came across following problem:

Consider below graph: What will be the shortest path tree starting with node $$A$$ returned by Dijkstra’s algorithm, if we assume priority queue is implemented as binary min heap?

My solution:

I referred Dijkstra from CLRS: With A as a starting node, we will have priority queue bin min heap as follows:

A{root, 0}     | Rest all:{∅,∞} 

(Notation: {parent in SPT, shortest path weight})

It will extract A from priority queue and add it to SPT and will relax AC and AB:

    B{A:5}      /  \ C{A:6}  Rest all:{∅,∞}  

It will extract B from priority queue and and add it to SPT:

   C{A:6}       | Rest all:{∅,∞}  

and will relax BE:

            C{A:6}              /   \ Rest all:{∅,∞}   E{B,6} 

Next it will extract C and so one. Thus the SPT will be: But not: Q1. Am I correct with above?
Q2. CLRS algo does not dictate which node to add to SPT if multiple of them have same shortest path weight. Hence its dependent on how priority queue is implemented. If no information was given about how priority queue was implemented then we cannot tell how SPT will be formed. Am I right?

Posted on Categories proxies

## Dijkstra’s algorithm chooses the closest unvisited node to visit next, what would happen if we didn’t do this?

Why is it necessary to always choose the closest vertex to the source to visit next?

Say instead of picking the closest vertex I pick the furthest. Can someone give an example of a graph where this would give the wrong answer?

Posted on Categories proxies

## When do we would like to use array as the data structure in Dijkstra’s algorithm instead of heap for perfmance

When do we would like to use array as the data structure in Dijkstra’s algorithm instead of heap for performance gain ?

Posted on Categories proxies

## Dijkstra’s Algorithm Question

I’m doing this assignment for my CS class. We’re suppose to implement Dijkstra’s Shortest Path Algorithm based off a worksheet.

My main questions/confusions are labeled with the blue numbers on the 3rd image.

2) How would I get the index of u in vertices given vertices is defined as a Vertex array?

3) How would I check if v of u? I’m also assuming u is the value stored in vertices at index ‘uIndex’.

4) How would I check the edge and would ‘alt’ be stored as an integer or a vertex?

Note I’ve been trying to implement this with Java. I’m just confused on the wording on this algorithm. I do not need an implementation of this code, mostly just answers to my questions above.   Posted on Categories proxies

## For what family of graphs does Dijkstra’s algorithm achieve the run-time upper bound

The question is in the title of the post. I am hoping to get some validation regarding my solution.

After some trial and error, my idea is as follows.

1. Worst case complexity of $$\mathcal{O}(E\lg_{}{V})$$ is achieved when nodes relax all of their neighbors when dequed.
2. For the above to occur, longer paths to every neighbor of $$v$$ must relax their respective edges into the said neighbors before $$v$$ is dequed.

The two points above give rise to the following formalism.

For all paths $$p$$, $$q$$ between any two nodes $$s$$ and $$t$$, $$l(p) > l(q) \implies l(p \setminus \{t\}) < l(q \setminus \{t\})$$ where $$l(x)$$ is the length of path $$x$$. For example, in the graph above, longer path edge $$A \rightarrow C$$ is relaxed before the edge $$B \rightarrow C$$ of the shorter path $$A \rightarrow B \rightarrow C.$$ This property is true for every node in the graph.

Posted on Categories proxies