Shortest pathway across a snakes and ladders board (Update) Earlier I posted a fairly inefficient recursive solution to the problem of getting across a snakes and ladders board in the smallest number of moves.

I have created a much faster solution to this using Dijkstra's algorithm and I believe it is correct. 

Each square on the board is linked to any square that is between 1-6 larger than it with a weight of one (equivalent of rolling a 1-6 on a dice). All snakes and ladders link squares with a weight of 1. The aim was to have the smallest total cost for the pathway between 1 and 100 (0 and 99 here as I have used list indexes). 

This is the first time I have implemented Dijkstra's algorithm and the first time I have used namedtuples. I am not sure if using namedtuples was appropriate, but it made it clearer in my head. 

I think I have massively over-complicated bits of code especially within the for loop under the condition if edge.start == next_item:. I seem to be using list comprehensions far too much and I know this makes the solution slower than it could be. Please could someone help me work out better ways to access the variables in my queue of named-tuples. 

"""Calculate the shortest path across a snakes and ladders board using Dijkstra's shortest path"""
from collections import namedtuple

Edge = namedtuple("Edge", ("start", "end", "cost"))
Stack = namedtuple("Stack", ("start", "pathcost", "totalcost"))


class Graph:
    """Class generates graph and calculates shortest path"""
    def __init__(self, edges):
        """Generate edges in graph"""
        self.edges = [Edge(*edge) for edge in edges]

    def dijkstra_path(self, start, end):
        """Function that calculates the shortest path"""
        if start &gt;= end or start &lt; 0 or end &gt; 99:
            return -1
        queue = sorted(
            (
                Stack(edge.end, edge.cost, edge.cost)
                for edge in self.edges
                if edge.start == start
            ),
            key=lambda x: x[2],
        )
        while queue:
            next_item, _, current_total = queue.pop(0)
            if next_item == end:
                return current_total
            for edge in self.edges:
                if edge.start == next_item:
                    if edge.end in [item.start for item in queue]:
                        current_cost = [
                            item.totalcost for item in queue if item.start == edge.end
                        ][0]
                        if not current_cost &lt; edge.cost + current_total:
                            queue = [item for item in queue if item.start != edge.end]
                            queue.append(
                                Stack(edge.end, edge.cost, edge.cost + current_total)
                            )
                    else:
                        queue.append(
                            Stack(edge.end, edge.cost, edge.cost + current_total)
                        )
            queue = sorted(queue, key=lambda x: x[2])


def build_graph():
    """Chess Board"""
    list_board = [[i, i + j, 1] for i in range(100) for j in range(1, 7)]
    # Ladders
    list_board.append([1, 37, 1])
    list_board.append([19, 59, 1])
    list_board.append([28, 63, 1])
    list_board.append([55, 99, 1])
    # Snakes
    list_board.append([91, 13, 1])
    list_board.append([86, 11, 1])
    list_board.append([53, 2, 1])
    list_board.append([41, 13, 1])
    return list_board

if __name__ == "__main__":
    GRAPH = Graph(build_graph())
    FROM = 0
    TO = 100
    NUMBER_STEPS = GRAPH.dijkstra_path(FROM, TO)
    if not NUMBER_STEPS == -1:
        print(f"Can complete game in a minimum of {NUMBER_STEPS} rolls")
    else:
        print("Error. Make sure the starting point is between 0 and 99 and less than the end point",
              "which itself must be than or equal to 99")
Named tuples are a good idea here. If you need to mutate the data you should instead use dataclasses.dataclass. But as there is no need here it's good.
I'd suggest changing your nodes to contain snakes, ladders, and the start and end of the board. This is as you don't need to build the empty spaces as they are only used as distances.

Since you need the distance between two nodes, then you need to calculate the distance at creation, not during the calculations.
I've simplified calculating the distance between each node. You should take into account the following special cases:


If the distance between two nodes is 12, and there is a snake or ladder halfway between them, it takes 3 rather than 2 turns to travel between the nodes.
If there are 6 snakes or ladders after a node it's impossible to pass them without visiting those nodes.

Currently you have Edge with a start, end and cost. I would suggest you instead split this into a Node with a start, end and edges. And an Edge that has a distance and a node.

It should be noted that the start and end should only be used when creating the graph. The node will then just turn into glorified list.
It should be noted that Node should be called Vertex if you want to keep with 'pure' graph theory naming.
Please ignore my implementation of Dijkstra's algorithm, it's not great. And half way I came across some hashing problems, hence the path[node[:2]] ickyness. I don't recommend you take inspiration from it - unless it's how not to code.

This means if the graph is setup, incorrectly, to have two ladders over the same space, then some bugs may appear.


All of this together can look like:

from collections import namedtuple
from dataclasses import dataclass, field
from typing import *  # Against best-practice but shhh
import math

Edge = namedtuple('Edge', 'distance node'.split())


class Node(namedtuple('Node', 'start end edges'.split())):
    def __str__(self):
        return f'{self.start} -&gt; {self.end}'


@dataclass(order=True)
class Path:
    distance: int
    current: Node=field(compare=False)
    previous: Node=field(compare=False)


@dataclass
class Graph:
    nodes: List[Node]

    def shortest_paths(self, start: Node) -&gt; Dict[Node, Path]:
        if start not in self.nodes:
            raise ValueError("Graph doesn't contain start node.")
        paths = {}
        queue = []
        for node in self.nodes:
            path = Path(float('inf'), node, None)
            paths[node[:2]] = path
            queue.append(path)

        paths[start[:2]].distance = 0
        queue.sort(reverse=True)
        while queue:
            node = queue.pop()
            for neighbor in node.current.edges:
                alt = node.distance + neighbor.distance
                path = paths[neighbor.node[:2]]
                if alt &lt; path.distance:
                    path.distance = alt
                    path.previous = node
            queue.sort(reverse=True)
        return paths

    def shortest_path(self, start: Node, end: Node) -&gt; List[Tuple[int, Node]]:
        if end not in self.nodes:
            raise ValueError("Graph doesn't contain end node.")
        paths = self.shortest_paths(start)
        node = paths[end[:2]]
        output = []
        while node is not None:
            output.append((node.distance, node.current))
            node = node.previous
        return list(reversed(output))


def build_nodes(snakes: List[Tuple[int, int]], size: int) -&gt; List[Node]:
    return [
        Node(1, 1, []),
        Node(size, size, [])
    ] + [
        Node(start, end, [])
        for start, end in snakes
    ]


# There are some edgecases that will need to be handled.
def calculate_distance(start: Node, end: Node, nodes: List[Node]):
    distance = int(math.ceil((end.start - start.end) / 6))
    start.edges.append(Edge(distance, end))


def add_edges(nodes: List[Node]):
    for start in nodes:
        for end in nodes:
            if end.start &gt; start.end:
                calculate_distance(start, end, nodes)


def build_graph(edges: List[Tuple[int, int]], size: int):
    nodes = build_nodes(edges, size)
    add_edges(nodes)
    start, end = nodes[:2]
    return Graph(nodes), start, end


if __name__ == '__main__':
    graph, start, end = build_graph(
        [
            (  2, 520),
            (530, 500),
            (510, 999)
        ],
        1000,
    )
    for dist, node in graph.shortest_path(start, end):
        print(dist, node)


This outputs:

0 1 -&gt; 1
1 2 -&gt; 520
3 530 -&gt; 500
5 510 -&gt; 999
6 1000 -&gt; 1000