10-08 Shortest

Skills base

• Sorting into a new container: ys = sorted(..., reverse=True)
• Sorting by mutation, changing the existing container: xs.sort(reverse=True)
• Field width: f"{x:10}" puts x in a space 10 characters wide.

Improvements to graph.py

• Define a type Vertex = int at the start.
• Make sure your class is called Graph.
• Write an insert edge method g.insert_edge(v,w) that inserts a normal edge connnecting v and w.

Distance Experiments

Setup:

from graph import Graph, Vertex
def add_random_edges(g: Graph, how_many: int) -> None:
    pass
def shortest_distances(g: Graph, start: Vertex) -> dict[Vertex, int]:
    pass

• Write the function add_random_edges.

• Write a function shortest_distances that returns a dictionary of the shortest distances (fewest possible edges) between the starting vertex and every other vertex.

• Demonstrate your shortest_distances function works by creating a random maze on 12 vertices (see below), then:

  1. Draw it on paper with no crossing edges.
  2. Manually track the shortest path to each of the vertices.
  3. Check that the shortest distances you get agree with your program.

Simple Maze Generator

You can use my maze generator or write one yourself. The code below just connects every vertex to a random vertex that is already connected to the “root” 0.

def mazegen(nvertices: int) -> Graph:
    used = [0]
    available = list(range(1, nvertices))
    random.shuffle(available)

    g = Graph(nvertices=nvertices)
    for y in available:
        x = random.choice(used)
        g.insert_edge(x, y)
            used.append(y)
    return g

Analyzing Mazes

Research question: when you add random edges to an existing maze, how are the shortest distances affected?

Experiment:

1. Generate a random graph (“maze”) with 2000 vertices.
2. Compute the shortest distances from 0 to every vertex.
3. Add 100 random edges to your graph.
4. Again, compute the shortest distances.
5. Analyze how much the shortest distances, producing a table of values showing a table of how much they change with the addition of 100 random edges.

Example output:

==== ALL CHANGES, ASCENDING ====
         0 1281
         1  192
         2  173
         3   96
         4  126
         5   35
         6   40
         7   19
         8   32
         9    5
        10    1

• ←Previous
Next→