Think Like Dijkstra to Solve Problems

Edsger Dijkstra, a renowned Dutch computer scientist, invented his namesake algorithm in the late 1950s. The story goes that Dijkstra devised the algorithm to solve a practical problem, but not one that involved computer networks or maps.

At the time, Dijkstra was living in the Netherlands and working at the Mathematical Center in Amsterdam. He often entertained guests at his home, and one night, after a social gathering, he had a thought: how could he provide each of his guests with a personalized travel itinerary to return home, taking into account the various transportation options and routes available?

To solve this problem, he started working on a method that would help determine the shortest paths between different points on a graph, representing the various travel options. He reportedly developed the basics of his algorithm on a whim one quiet afternoon, scribbling calculations on a piece of paper.

Dijkstra’s algorithm became one of his most famous contributions to the field of computer science. Its elegance and practicality have made it a fundamental tool in network routing, geographical mapping, and many other fields where optimal pathfinding is crucial.

Interestingly, it took almost a decade after Dijkstra’s initial formulation for his algorithm to be widely recognized. His algorithm, initially considered theoretical, found practical applications with the advent of computer networks in the late 1960s. The efficiency and simplicity of Dijkstra’s algorithm made it an excellent tool for routing data across these networks – a purpose that it continues to serve today.

However, it’s worth noting that Dijkstra, ever the theoretician, once famously said:

Computer Science is no more about computers than astronomy is about telescopes.

His work, including the development of his famous algorithm, was always about the broader principles and structures that underpin computation, not just their practical applications. His impact on the field continues to be felt to this day, and his algorithm remains a fundamental part of the computer science curriculum worldwide.

Thinking

Thinking like Dijkstra, or any problem-solving computer scientist, requires a blend of systematic thinking, mathematical reasoning, and a bit of creativity. Here are some ways to cultivate a mindset like Dijkstra’s:

  1. Start with Simple Cases: Try to understand the problem in its simplest form first. Then, build up the complexity step by step. By understanding the simple cases, you can often see patterns or principles that apply to more complex situations.

  2. Think Abstractly: Try to abstract the problem from its specifics. Instead of focusing on the details, identify the underlying principles or patterns. This can help you see the problem in a new light, and potentially identify more general solutions.

  3. Use Rigorous Logic: Dijkstra was a strong advocate of formal reasoning in computer science. Be rigorous in your thought process and use logical reasoning to approach the problem. Make sure every step is logically sound and can be justified.

  4. Think Recursively: Many of Dijkstra’s most famous algorithms, including his shortest path algorithm, make use of recursion. Try to think about how you could break the problem down into smaller, similar problems.

  5. Visualize: Dijkstra used graphs to visualize his shortest path algorithm. Visualizations can be a powerful tool to understand a problem and its potential solutions. Draw diagrams, flowcharts, or even use physical objects to represent your problem and the possible solutions.

  6. Iterate: Don’t expect to find the perfect solution on your first try. Instead, aim for a good solution, then refine it, and refine it again. Each iteration brings you closer to the best solution.

  7. Focus on Elegance: Dijkstra valued elegance in his algorithms, where elegance is a blend of simplicity, effectiveness, and efficiency. Aim for solutions that are straightforward, clear, and efficient.

Remember that becoming a problem solver takes time and practice. The more problems you tackle, the better you’ll become at it. It’s about building a mindset and developing a set of tools that you can apply to any problem you encounter. As Dijkstra himself put it:

Perfecting oneself is as much unlearning as it is learning.

Unlearning

“Perfecting oneself is as much unlearning as it is learning” is a philosophical statement that speaks to the continuous nature of personal growth and development. Here’s a deeper explanation:

  1. Learning: This refers to the acquisition of new knowledge, skills, behaviors, and attitudes. It’s the process by which we add to our understanding of the world around us, adapt to new situations, and equip ourselves to face new challenges. Learning is fundamental to growth and improvement.

  2. Unlearning: This is perhaps a less familiar concept. Unlearning refers to the process of recognizing and letting go of outdated, incorrect, or unhelpful knowledge or habits. Over time, we often accumulate beliefs, attitudes, or practices that may have served us at one point but no longer do. In some cases, what we think we know might actually be wrong or incomplete. Unlearning is about identifying these areas and consciously deciding to move past them.

When we say “perfecting oneself,” we’re talking about the ongoing process of self-improvement and personal growth. This involves both learning new things and unlearning old things that hold us back.

For example, if you have learned to respond to stress by procrastinating, part of perfecting your response to stress will involve unlearning that habit. You’ll have to recognize that it’s an unhelpful coping mechanism and learn new, healthier ways to deal with stress.

In this way, the path to personal perfection is a balance of both learning and unlearning. It’s about gaining new knowledge and insights, but also about challenging your existing perceptions and letting go of what no longer serves you.

Language Agnostic Coding Drills

The Dijkstra’s Shortest Path Algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.

Here’s a list of units of learning, arranged in increasing level of difficulty:

  1. Understanding Graphs: Familiarize yourself with the concept of graphs, including nodes (or vertices) and edges. Learn about weighted graphs, where each edge has an associated cost or “weight”.

  2. Data Structures: Understanding the usage of data structures like arrays/lists, sets, and dictionaries (or maps), and how to perform operations on them.

  3. Priority Queue: Learn what a priority queue is and how to use it. In the context of Dijkstra’s algorithm, the priority queue is used to keep track of the node with the shortest tentative distance.

  4. Initialization: Learn to initialize variables and data structures needed for the algorithm: distances, visited nodes, and the priority queue.

  5. Loops and Conditionals: Learn how to control program flow with loops and conditionals.

  6. Graph Traversal: Understand the process of visiting nodes of the graph and updating the tentative distances.

  7. Updating Distances: Understand how to update the shortest distances to each node.

  8. Dijkstra’s Algorithm: Learn how all these components come together in Dijkstra’s algorithm. Understanding the overall flow and logic of the algorithm.

For each unit, you’d want to practice writing and understanding code snippets that implement the concept, before trying to combine them in the final algorithm.

Solution for Coding Drills in Python

Here are the Python solutions corresponding to each of the above units of learning.

  1. Understanding Graphs: A simple representation of a weighted graph using a dictionary where the keys are the nodes and the values are dictionaries of adjacent nodes and their corresponding edge weights.
1
2
3
4
5
6

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
  1. Data Structures: List, Set, and Dictionary in Python
1
2
3
4
5
6
7
8

# List
my_list = [1, 2, 3, 4, 5]

# Set
my_set = {1, 2, 3, 4, 5}

# Dictionary
my_dict = {'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5}
  1. Priority Queue: Using heapq library in Python
1
2
3
4
5
6
7
8
9

import heapq

# create a priority queue
pq = []
heapq.heappush(pq, (2, 'A'))
heapq.heappush(pq, (1, 'B'))

# pop the smallest element
smallest = heapq.heappop(pq)
  1. Initialization:
1
2
3
4
5

def initialize(graph, start_node):
    distance = {node: float('infinity') for node in graph}
    distance[start_node] = 0
    pq = [(0, start_node)]
    return distance, pq

  1. Loops and Conditionals: Implemented throughout the algorithm.

  2. Graph Traversal:

1
2

while pq:
    _, current_node = heapq.heappop(pq)
  1. Updating Distances:
1
2
3
4
5
6

for neighbour, weight in graph[current_node].items():
    old_distance = distance[neighbour]
    new_distance = distance[current_node] + weight
    if new_distance < old_distance:
        distance[neighbour] = new_distance
        heapq.heappush(pq, (new_distance, neighbour))
  1. Dijkstra’s Algorithm: Putting it all together:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import heapq

def dijkstra(graph, start_node):
    # Initialization
    distance = {node: float('infinity') for node in graph}
    distance[start_node] = 0
    pq = [(0, start_node)]

    while pq:
        _, current_node = heapq.heappop(pq)

        for neighbour, weight in graph[current_node].items():
            old_distance = distance[neighbour]
            new_distance = distance[current_node] + weight

            if new_distance < old_distance:
                distance[neighbour] = new_distance
                heapq.heappush(pq, (new_distance, neighbour))

    return distance