# Dijkstra

shortest path to x with weighted graphs

shortest path to x with unweighted graph use breadth-first search

only works for DAGs. cannot have negative weighted edges (use Bellman-Ford algorithm) because a node cannot be reprocessed

table of the cost (how expensive it is to get to there) of each node

1. find cheapest node from the costs table
2. check if there is a cheaper path to neighbors, update costs table and parent table if there is
3. mark node as processed
4. repeat for every node in the graph
5. calculate final path using parent table

## Dijkstra’s in Java

``````import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DijkstrasAlgorithm {
// the graph
private static Map<String, Map<String, Double>> graph = new HashMap<>();
private static List<String> processed = new ArrayList<>();

private static String findLowestCostNode(Map<String, Double> costs) {
Double lowestCost = Double.POSITIVE_INFINITY;
String lowestCostNode = null;

// Go through each node
for (Map.Entry<String, Double> node : costs.entrySet()) {
Double cost = node.getValue();
// If it's the lowest cost so far and hasn't been processed yet...
if (cost < lowestCost && !processed.contains(node.getKey())) {
// ... set it as the new lowest-cost node.
lowestCost = cost;
lowestCostNode = node.getKey();
}
}

return lowestCostNode;
}

public static void main(String[] args) {
graph.put("start", new HashMap<>());
graph.get("start").put("a", 6.0);
graph.get("start").put("b", 2.0);

graph.put("a", new HashMap<>());
graph.get("a").put("fin", 1.0);

graph.put("b", new HashMap<>());
graph.get("b").put("a", 3.0);
graph.get("b").put("fin", 5.0);

graph.put("fin", new HashMap<>());

// The costs table
Map<String, Double> costs = new HashMap<>();
costs.put("a", 6.0);
costs.put("b", 2.0);
costs.put("fin", Double.POSITIVE_INFINITY);

// the parents table
Map<String, String> parents = new HashMap<>();
parents.put("a", "start");
parents.put("b", "start");
parents.put("fin", null);

String node = findLowestCostNode(costs);
while (node != null) {
Double cost = costs.get(node);
// Go through all the neighbors of this node

Map<String, Double> neighbors = graph.get(node);

for (String n : neighbors.keySet()) {
double newCost = cost + neighbors.get(n);
// If it's cheaper to get to this neighbor by going through this node
if (costs.get(n) > newCost) {
// ... update the cost for this node
costs.put(n, newCost);
// This node becomes the new parent for this neighbor.
parents.put(n, node);
}
}
// Mark the node as processed

// Find the next node to process, and loop
node = findLowestCostNode(costs);
}

System.out.println("Cost from the start to each node:");
System.out.println(costs); // { a: 5, b: 2, fin: 6 }
}
}``````

## Dijkstra’s in Python

``````# the graph
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}

# the costs table
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# the parents table
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

processed = []

def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
# Go through each node.
for node in costs:
cost = costs[node]
# If it's the lowest cost so far and hasn't been processed yet...
if cost < lowest_cost and node not in processed:
# ... set it as the new lowest-cost node.
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node

# Find the lowest-cost node that you haven't processed yet.
node = find_lowest_cost_node(costs)
# If you've processed all the nodes, this while loop is done.
while node is not None:
cost = costs[node]
# Go through all the neighbors of this node.
neighbors = graph[node]
for n in neighbors.keys():
new_cost = cost + neighbors[n]
# If it's cheaper to get to this neighbor by going through this node...
if costs[n] > new_cost:
# ... update the cost for this node.
costs[n] = new_cost
# This node becomes the new parent for this neighbor.
parents[n] = node
# Mark the node as processed.
processed.append(node)
# Find the next node to process, and loop.
node = find_lowest_cost_node(costs)

print "Cost from the start to each node:"
print costs``````