# Questions tagged [dijkstras-algorithm]

The tag has no usage guidance.

24 questions
Filter by
Sorted by
Tagged with
23 views

### Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph

As discussed here Johnson's Algorithm can be used to solve the APSP-Problem in $O(V^2\log V + VE)$ in stead of $O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the ...
44 views

### Find every path that passes through certain edges

I'm faced with the following problem: Given Directed and unweighted graph, where each edge E has two attributes Goal Find every path through the 3 (or more) given edges in a specific order ...
13 views

### Trivial clarification with the analysis of the Dijkstra Algorithm as dealt with in Keneth Rosen's “Discrete Mathematics and its Application”

I was going through the text, "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the analysis of the Dijkstra Algorithm and felt that the values at some places ...
For a given graph $G=(V,E)$ and path $p= v_1 \to v_2 \to ...\to v_k$, $w^\ast(p)$ represents the weight of the path between $v_1$ and $v_k$ excluding max_edge. w^\ast(p) = \sum_{i=1}^{k-1} w(v_i, v_{...