Graph Theory & Networks

Explore connected graph topologies and computational routing bounds. Build paths to cities, drag nodes to reshape coordinates, and step Dijkstra's algorithm.

Dijkstra Routes

Delivery Network Puzzle

A network consists of vertices (nodes) and weighted edges (roads). In **Puzzle mode**, click nodes sequentially to route a truck from Start (Node A) to Destination (Node F). In **Stepper mode**, watch Dijkstra execute step-by-step.

Nodes can be dragged to reposition. In Puzzle mode, click on connected nodes starting at A to build your path.

Current Path Cost

Path: A → C (Cost: 2)
Objective: Reach Node F with minimum weight cost.
Click Node C or Node B to begin routing from Start Node A.
Target Optimal Cost: **8**
Anatomy Specs

Vertices, Edges & Complexity

Network structures connect discrete configurations. Nodes represent locations, and edges represent communication routes.

Graph Topology Rules


Degree of a Vertex:
The number of edges connected to a node. Node B has a degree of 4, connected to edges A-B, B-C, B-D, and B-E.
Trees and Cycles:
A **Tree** is a connected graph containing no cycles. A tree with V vertices always contains exactly **V - 1** edges.
Edge Weighting:
Edges represent path costs (latency, distance, weight). Algorithms optimize traversal by summing edge weights.

Dijkstra Algorithm Details


Algorithm Operation:
Dijkstra operates greedily, continuously expanding the unvisited node with the lowest distance estimate, relaxing its outgoing edges, and closing the node.
Time Complexity:
- With Binary Heap Priority Queue: **O((V + E) log V)**
- With Unsorted Array Queue: **O(V²)**
Negative Constraint:
Dijkstra's greedy finalized closure assumes non-negative edge weights. It fails on graphs with negative weights (requiring Bellman-Ford).
Self Evaluation

Graph Theory Quiz

Assess your theoretical grasp of vertices, edges, trees, and Dijkstra's algorithm.

Question 1 of 5 Score: 0/0

In graph theory, what does the degree of a vertex represent?

Correct Answer!

Explanation goes here.

Focus Area Vocabulary


  • Vertex: A node representing an junction, city, or coordinate item.
  • Edge: A connection line between vertices, containing a weight factor.
  • Relaxation: Updating a neighbor node's distance estimate if a shorter path is found.