Chapter 7: Dijkstra's Algorithm

There are four steps to Dijkstra’s algorithm:

• Find the “cheapest” node. This is the node you can get to in the least amount of time.

• Update the costs of the neighbors of this node.

• Repeat until you’ve done this for every node in the graph.

• Calculate the final path.

Collection:

• Each edge in the graph has a number associated with it. These are called weights.

• A graph with weights is called a weighted graph. A graph without weights is called an unweighted graph.

• To calculate the shortest path in an unweighted graph, use breadth-first search. To calculate the shortest path in a weighted graph, use Dijkstra’s algorithm.

• Dijkstra’s algorithm only works with directed acyclic graphs, called DAGs for short.

• That assumption only works if you have no negative-weight edges. So you can’t use negative-weight edges with Dijkstra’s algorithm.

• If you want to find the shortest path in a graph that has negative-weight edges, there’s an algorithm for that! It’s called the Bellman-Ford algorithm.

Implementation

def find_lowest_cost_node(costs):
    lowest_cost = float(“inf”)
    lowest_cost_node = None
    for node in costs:
          cost = costs[node]
        if cost < lowest_cost and node not in processed:
          lowest_cost = cost
                    lowest_cost_node = node
    return lowest_cost_node