Master Hash Tables, Heaps, and Graph Algorithms: From Basics to Dijkstra

Data structures and algorithms are core subjects in computer science, providing the foundation for abstract data storage and computation; mastering them is essential for selecting appropriate structures and algorithms to solve business and data problems.

1. Hash Table

A hash table (or hash map) stores key‑value pairs by applying a hash function to the key to compute an array index, enabling fast element lookup. The hash function maps a key to an integer, which is then reduced modulo the array length to obtain the storage slot.

Java collections such as HashMap and Hashtable are built on this principle. While lookup is fast, insertion and deletion can be slower, so many implementations use chaining (an array of linked lists) or, in newer JDK versions, a combination of arrays and red‑black trees.

2. Heap

A heap is a special tree‑based data structure represented as an array. In a heap, each node’s value is either not greater than (min‑heap) or not less than (max‑heap) its parent’s value, and the structure forms a complete binary tree.

Common heap variants include binary heaps and Fibonacci heaps. Heaps are often used for heap sort and priority queues.

3. Graph

A graph consists of a finite set of vertices V and a set of edges E. Vertices may be called nodes, and edges are ordered pairs of vertices. Graphs can be directed or undirected.

Shortest Path Problem

The goal is to find the path with the minimum sum of edge weights between two vertices in a network.

Shortest Path (Shortest Path)

Source vertex (Source)

Destination vertex (Destination)

1) Single‑source shortest path in an unweighted graph

Can be solved with Breadth‑First Search (BFS).

2) Single‑source shortest path in a weighted graph

Dijkstra’s algorithm solves the problem for graphs with non‑negative edge weights.

3) All‑pairs shortest path (Floyd)

Published by Robert Floyd in 1962, the Floyd‑Warshall algorithm iteratively considers each vertex as an intermediate node to improve path lengths.

Minimum Spanning Tree (MST)

An MST connects all vertices with the minimum total edge weight using a greedy approach.

Prim’s Algorithm

Starts from a random vertex and repeatedly adds the cheapest edge that expands the growing tree.

Kruskal’s Algorithm

Builds a forest of trees and merges them by adding the smallest edges that do not create cycles.

Topological Sorting

A topological order is a linear ordering of vertices such that for every directed edge u→v, u appears before v. It is used for scheduling tasks represented as a Directed Acyclic Graph (DAG).

Dijkstra Algorithm Implementation (Java)

package 图论;
import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class dijkstra {
    static class node {
        int x; //节点编号
        int lenth; //长度
        public node(int x, int lenth) {
            this.x = x;
            this.lenth = lenth;
        }
    }
    public static void main(String[] args) {
        int[][] map = new int[6][6]; //记录权值，顺便记录链接情况
        initmap(map);
        boolean[] bool = new boolean[6]; //判断是否已经确定
        int[] len = new int[6];
        for (int i = 0; i < 6; i++) {
            len[i] = Integer.MAX_VALUE;
        }
        Queue<node> q1 = new PriorityQueue<>(com);
        len[0] = 0; //从0这个点开始
        q1.add(new node(0, 0));
        int count = 0; //计算执行了几次dijkstra
        while (!q1.isEmpty()) {
            node t1 = q1.poll();
            int index = t1.x; //节点编号
            int length = t1.lenth; //节点当前点距离
            bool[index] = true; //抛出的点确定
            count++;
            for (int i = 0; i < map[index].length; i++) {
                if (map[index][i] > 0 && !bool[i]) {
                    node node = new node(i, length + map[index][i]);
                    if (len[i] > node.lenth) {
                        len[i] = node.lenth;
                        q1.add(node);
                    }
                }
            }
        }
        for (int i = 0; i < 6; i++) {
            System.out.println(len[i]);
        }
    }
    static Comparator<node> com = new Comparator<node>() {
        public int compare(node o1, node o2) {
            return o1.lenth - o2.lenth;
        }
    };
    private static void initmap(int[][] map) {
        map[0][1] = 2; map[0][2] = 3; map[0][3] = 6;
        map[1][0] = 2; map[1][4] = 4; map[1][5] = 6;
        map[2][0] = 3; map[2][3] = 2;
        map[3][0] = 6; map[3][2] = 2; map[3][4] = 1; map[3][5] = 3;
        map[4][1] = 4; map[4][3] = 1;
        map[5][1] = 6; map[5][3] = 3;
    }
}

In summary, hash tables and heaps provide efficient data lookup and ordering, while graph structures enable solving optimization problems such as shortest‑path routing, critical‑path analysis, and scheduling through algorithms like Dijkstra, Floyd‑Warshall, MST, and topological sorting.