Skip to content

About

This repository contains a Java implementation of Dijkstra’s Algorithm for finding the shortest paths from a given source vertex in a weighted graph. The program reads a graph with integer edge weights from a file, constructs the Dijkstra shortest-path spanning tree, and outputs a formatted representation of the results.

Topics

Resources

Stars

1 star

Watchers

0 watching

Forks

Latest commit

 

History

4 Commits

Folders and files

Repository files navigation

Dijkstra's Algorithm — Java

Shortest-path spanning tree on a weighted undirected graph, built from scratch.



Graph (source = 5):          Spanning tree result:

    4       2                 Vertex  Dist  Prev
1 ─── 2 ─── 3                  1      3     5
│  8  │  1  │                  2      7     1
│     │     │                  3      6     4
5 ─── 2 ─── 4 ─── 6            4      5     5
  3     5     3                 5     [src]  —
  └─────────────7──┘            6      7     5

What It Does

Reads a weighted undirected graph from a file, runs Dijkstra's algorithm from a specified source vertex, and writes the resulting shortest-path spanning tree — each vertex's distance from the source and its predecessor — to an output file.


Algorithm

Uses an adjacency matrix and an iterative greedy selection loop:

1. Initialize all distances to ∞, source distance to 0
2. Repeat V times:
   a. Pick the unvisited vertex u with the minimum current distance
      → Tie-break: always choose the lower-numbered vertex
   b. Mark u as visited
   c. For each unvisited neighbor v of u:
      if dist[u] + weight(u,v) < dist[v]:
          dist[v] = dist[u] + weight(u,v)
          prev[v] = u
3. Output dist[] and prev[] for every vertex

Time complexity: O(V²) with adjacency matrix — appropriate for dense graphs.


Input / Output Format

Input (cop3503-dijkstra-input.txt):

6        ← number of vertices
5        ← source vertex (1-indexed)
9        ← number of edges
1 2 4    ← v1  v2  weight
1 5 3
2 3 2
...

Output (cop3503-dijkstra-output-hernandez-santiago.txt):

6
1 3 5    ← vertex  distance  predecessor
2 7 1
3 6 4
4 5 5
5 -1 -1  ← source: distance=0 represented as -1, no predecessor
6 7 5

Run It

javac Dijkstra.java
java Dijkstra

Place cop3503-dijkstra-input.txt in the same directory. Output is written automatically.


Bugs Fixed from Original Approach

# Bug Impact Fix
1 Next-vertex selection only scanned neighbors of the current vertex, not all unvisited vertices globally Produced wrong shortest paths on most non-trivial graphs Replaced with a full scan of all unvisited vertices each iteration
2 Recursive implementation — one stack frame per vertex StackOverflowError on graphs with more than ~500 vertices Rewrote as iterative loop
3 No tie-breaking logic on equal distances Non-deterministic output; failed the "lower-numbered vertex" requirement Inner loop scans vertices in ascending order; first match at minimum distance wins
4 Source vertex predecessor and output format inconsistent Source row could print 0 instead of -1 -1 Source vertex detected explicitly and printed as -1 -1

Java Adjacency Matrix Greedy Shortest Path

UCF COP 3503 Computer Science II — Fall 2024 (Optional Extra Credit)

About

This repository contains a Java implementation of Dijkstra’s Algorithm for finding the shortest paths from a given source vertex in a weighted graph. The program reads a graph with integer edge weights from a file, constructs the Dijkstra shortest-path spanning tree, and outputs a formatted representation of the results.

Topics

Resources

Stars

1 star

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages