My Dijkstra shortest path implementation was correct, it turned out. The problem is that the graph I gave in was intended to be undirected, but I didn't mutualize the edges between nodes. So, Node 1 would point to Node 2, but Node 2 didn't point back to Node 1.
As a result, it would often give me long distances for the shortest path between two nodes, then I'd look at the graph and see an obvious path that was way shorter than that. That's because it couldn't actually take that path because some of the nodes in it were one-way.
Once I fixed this, it worked. Gotta check the input data!