# What edge case am I missing for Dijkstra’s algorithm?

This is my Dijkstra’s implementation. It’s passing all cases in the pytest `input.n.txt` files but when I submit to the grading software (that doesn’t provide the test or any output) I get an invalid result. Here’s my solution (passes all provided test cases, but not hidden ones).

```# Uses python3

import queue
import sys
from math import inf

seen = set([s])

dist[s] = 0

prev[s] = s

q = queue.Queue()
q.put(s)

while not q.empty():

n = q.get()
# print(n)

edges = []

for i, edge in enumerate(edges):
d = dist[n] + edge
if d < dist[edge]:
dist[edge] = d
edge = d
prev[edge] = n

edges = sorted(edges, key=lambda x: x)
for (e, w) in edges:
if not e in seen:
q.put(e)

# print(dist)

# print(prev)

return dist[t] if dist[t] is not inf else -1

def parse(input):
data = list(map(int, input.split()))
n, m = data[0:2]
data = data[2:]
edges = list(zip(zip(data[0 : (3 * m) : 3], data[1 : (3 * m) : 3]), data[2 : (3 * m) : 3]))
data = data[3 * m :]
adj = [[] for _ in range(n)]
cost = [[] for _ in range(n)]
for ((a, b), w) in edges:
cost[a - 1].append(w)
s, t = data - 1, data - 1

if __name__ == "__main__":
print(parse(input))

def test_parse():
```

The format of the input is as follows…

```number_of_vertices number_of_edges
from to weight
from to weight
start end
```

input.txt

```4 4
1 2 1
4 1 2
2 3 2
1 3 5
1 3
```

input.1.txt

```5 9
1 2 4
1 3 2
2 3 2
3 2 1
2 4 2
3 5 4
5 4 1
2 5 3
3 4 4
1 5
```

input.2.txt

```3 3
1 2 7
1 3 5
2 3 2
3 2
```

input.3.txt

```5 5
1 2 1
1 3 2
2 3 1
2 4 6
3 4 1
1 4
```

input.4.txt

```5 6
1 2 1
1 3 2
2 3 1
2 4 6
3 4 1
1 1 2
1 1
```

input.5.txt

```4 4
1 2 1
2 3 1
3 4 1
4 1 1
1 1
```

My program passes ALL of these. And I’ve tried messing around with all the edge cases I can think of testing but still it fails with a “Wrong answer” error in the testing software.

One of the comments of the thread of somebody who DID solve it:

Wow! I really struggled to put this one together, not because I didn’t understand the Dijkstra algorithm but because of the difficulty in adjusting the priority of an item already added to a Python PriorityQueue class (whose use was implied by importing queue in the start code) or by keeping track of its position in the priority queue, which made translating the algorithm, as presented in the lectures, verbatim difficult.

In case it is helpful to others, the way I got around this was to move from thinking in terms of inserting vertices to the priority queue to inserting references to the vertices, with most updated distance at the time of insertion as the priority, instead. That way we don’t need to adjust the priority of an item already added to the queue at a later time.

We may end up inserting several references to the same vertex to the queue, but we will, of course, encounter the reference with the least distance first, and we can ignore any future references to the same vertex that we might encounter afterwards. Further, we can abort the algorithm as soon as we’ve popped a reference to the destination vertex.

This still runs pretty efficiently (for me, a maximum time of about a twentieth of that allowed), and is, in retrospect, a small adjustment in viewing the problem.