hard Graph Algorithms

Dijkstra Delivery Router

The Brief

A regional logistics firm runs lorries between depots and is haemorrhaging fuel money on suboptimal routes. Their dispatcher just types in the source and destination and a human picks the route by gut feel. You have been brought in to build the routing engine that will slot into their dispatch system.

Given a weighted directed graph of depots (where edge weights are journey time in minutes), implement Dijkstra's algorithm from scratch — no networkx, no scipy. Return both the shortest distance and the actual path. Then layer on a multi-stop optimiser: given a list of mandatory stops in any order, find the cheapest tour starting and ending at the depot.

Acceptance Criteria

Tap a criterion to mark it off as you work. Tap a category header to expand or collapse.

1 Array

2 Array

3 Array

4 Array

💡 Hints 0 / 5

Guest Mode Attempt this challenge freely, or log in to earn EXP & CodeCoins.

solution.py

Python 3

import heapq
import math
from itertools import permutations


class Graph:
    def __init__(self, directed=True):
        # TODO: store directed flag, init adjacency dict
        pass

    def add_edge(self, u, v, weight):
        # TODO: validate weight > 0, add edge(s)
        pass

    def shortest_path(self, source, target):
        """Return (distance, path_list)."""
        # TODO: Dijkstra with heapq, predecessors map
        pass

    def shortest_paths_from(self, source):
        """Return {node: (distance, path)}."""
        pass

    def optimal_tour(self, depot, stops):
        """Return (total_time, ordered_stops_including_return)."""
        # TODO: shortest paths between all (depot+stops) pairs, try permutations
        pass

Console