> For the complete documentation index, see [llms.txt](https://haroldyin.gitbook.io/grokking-algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://haroldyin.gitbook.io/grokking-algorithm/chapter-7-dijkstras-algorithm.md).

# 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

```python
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
```