Is Dijkstra's algorithm for directed or undirected graphs?

Question

I keep trying to google this, but the results I'm finding are just adding to my confusion. It seems that it can be possibly used for both? If so, which is it designed for by default and what needs to change to make it work the non-default way (whether that be directed or undirected)?

Edit: for reference, I had a problem last semester where I was given a list like this (airports):

AER,KZN,1.8835
ASF,KZN,1.3005
ASF,MRV,1.1204
CEK,KZN,1.9263
CEK,OVB,1.6733
DME,KZN,1.7892
DME,NBC,2.2319
DME,UUA,2.3786
EGO,KGD,1.4649
EGO,KZN,1.2603
GYD,NBC,2.0755

I was told it was directed, and asked to find the shortest path. I put it into a Dijkstra's algorithm I found on Github (it was an open-computer midterm so we didn't have nearly enough time to write the algorithm from scratch) and my professor said the shortest path it returned was incorrect and that it was not even a possible path because the list was supposed to be directed. I wasn't sure if I was supposed to then modify the algorithm or the list to make this correction. It ended up being the case that the 2nd shortest path it returned was actually the directed shortest path, but I'm still wondering what the problem was.

Answer 1

It can be applied to both. Here is why:

An undirected graph is basically the same as a directed graph with bidirectional connections (= two connections in opposite directions) between the connected nodes.

So you don't really have to do anything to make it work for an undirected graph. You only need to know all of the nodes that can be reached from every given node through e.g. an adjacency list.

Answer 2

Djikstras algorithm is typically for Positive weighted graphs. Perhaps you are confusing it with the breadth first search (BFS) algorithm, which is essentially Djikstras for unweighted graphs. The difference (between Djikstras and BFS), is when you are dealing with weighted paths, we must now consider the path costs adjustments (weights) & the decisions on which nodes to visit after the current.

Answer 3

You can use Dijkstra's algorithm in both directed and undirected graphs, because you simply add nodes into the PriorityQueue when you have an edge to travel to from your adjacency list. For example, if one of my nodes has an edge from A to B of weight 3, then if it's directed from B I won't be able to add the edge back into A, while from A I could add it to B.

Like the other answers, make sure you do not confuse it with weights. Dijkstra's algorithm runs on positive weighed graphs, otherwise the priority queue would be useless.

In your example, Dijkstra's algorithm would work because the graph is both weighed (positively) and has directed edges.

The fault would have been that the edges have been double-assigned in the form of an undirected graph. You should be careful when parsing the edges at the beginning into your objects to not duplicate the edges in the adjacency list.