Repository: dominikbraun/graph
Pull request #11 (2022-06-30 19:26:21)

Implement Dijkstra's algorithm for finding shortest paths


Patch:
diff --git a/README.md b/README.md
index 1d0c862..ddd470f 100644
--- a/README.md
+++ b/README.md
@@ -13,10 +13,10 @@ It supports different kinds of graphs such as directed graphs, acyclic graphs, o
 * Pathfinding algorithms, considering edge weights where appropriate:
   * [ ] Hamiltonian paths and cycles
   * [ ] Eulerian paths and cycles
-  * [ ] Dijkstra's algorithm
-  * [x] Tarjan's SCC algorithm
+  * [x] Shortest path (Dijkstra)
+  * [x] Strongly connected components (Tarjan)
 
-> Status: Work in progress. Multigraphs aren't supported at the moment.
+> Status: Work in progress. Multigraphs aren't supported.
 
 # Getting started
 
@@ -149,6 +149,24 @@ fmt.Println(scc)
 [[1 2 5] [3 4 8] [6 7]]
 ```
 
+## Find the shortest path
+
+![shortest path algorithm](img/dijkstra.svg)
+
+```go
+g := graph.New(graph.StringHash, graph.Weighted())
+
+// Add vertices and weighted edges ...
+
+path, _ := g.ShortestPath()
+
+fmt.Println(path)
+```
+
+```
+[A C E B]
+```
+
 ## Cycle checks for acyclic graphs
 
 ![cycle checks](img/cycles.svg)
@@ -160,8 +178,8 @@ g.Vertex(1)
 g.Vertex(2)
 g.Vertex(3)
 
-_ _= g.Edge(1, 2)
-_ _= g.Edge(1, 3)
+_ = g.Edge(1, 2)
+_ = g.Edge(1, 3)
 
 if err := g.Edge(2, 3); err != nil {
     panic(err)
diff --git a/collection.go b/collection.go
new file mode 100644
index 0000000..036ada8
--- /dev/null
+++ b/collection.go
@@ -0,0 +1,94 @@
+package graph
+
+import (
+	"errors"
+	"sort"
+)
+
+// priorityQueue is a priority queue implementation for minimum priorities, meaning that smaller
+// values will be prioritized. It maintains an descendently ordered list of priority items.
+//
+// This is still a naive implementation, which is to be replaced with a binary heap implementation.
+type priorityQueue[T comparable] struct {
+	items []priorityItem[T]
+}
+
+// priorityItem is an item in the priority queue, consiting of a priority and an actual value.
+type priorityItem[T comparable] struct {
+	value    T
+	priority float64
+}
+
+func newPriorityQueue[T comparable]() *priorityQueue[T] {
+	return &priorityQueue[T]{
+		items: make([]priorityItem[T], 0),
+	}
+}
+
+// Push pushes a new item with the given priority into the queue. Because Push keeps track of the
+// descendant order of items and priorities, it has O(n) insertion time.
+func (p *priorityQueue[T]) Push(item T, priority float64) {
+	index := p.Len() - 1
+
+	for i := p.Len(); i > 0; i-- {
+		currentItem := p.items[i-1]
+		if currentItem.priority > priority {
+			index = i
+			break
+		}
+	}
+
+	p.insertItemAt(item, priority, index)
+}
+
+// Pop returns the item with the smallest priority from the queue and removes that item. Returns an
+// error if the priority queue is empty, which can be tested using Len first.s
+func (p *priorityQueue[T]) Pop() (T, error) {
+	var priorityItem priorityItem[T]
+
+	if p.Len() == 0 {
+		return priorityItem.value, errors.New("priority queue is empty")
+	}
+
+	priorityItem = p.items[p.Len()-1]
+	p.items = p.items[:p.Len()-1]
+
+	return priorityItem.value, nil
+}
+
+// DecreasePriority decreases the priority of a given item to the given priority. The item must be
+// pushed into the queue first. If the item doesn't exist, nothing happens.
+//
+// With the current implementation, DecreasePriority causes the items in the queue to be re-sorted.
+func (p *priorityQueue[T]) DecreasePriority(item T, priority float64) {
+	for i, currentItem := range p.items {
+		if currentItem.value == item {
+			p.items[i].priority = priority
+		}
+	}
+
+	sort.Slice(p.items, func(i, j int) bool {
+		return p.items[i].priority > p.items[j].priority
+	})
+}
+
+// Len returns the current length of the priority queue, i.e. the number of items in the queue.
+func (p *priorityQueue[T]) Len() int {
+	return len(p.items)
+}
+
+func (p *priorityQueue[T]) insertItemAt(item T, priority float64, index int) {
+	priorityItem := priorityItem[T]{
+		value:    item,
+		priority: priority,
+	}
+
+	if p.Len() == 0 || p.Len() == index {
+		p.items = append(p.items, priorityItem)
+		return
+	}
+
+	p.items = append(p.items[:index+1], p.items[index:]...)
+
+	p.items[index] = priorityItem
+}
diff --git a/directed.go b/directed.go
index 15cbe54..bcc40be 100644
--- a/directed.go
+++ b/directed.go
@@ -334,6 +334,72 @@ func (d *directed[K, T]) findSCC(vertexHash K, state *sccState[K]) {
 	}
 }
 
+// ShortestPath computes the shortest path between two vertices and returns the hashes of the
+// vertices forming that path. The current implementation uses Dijkstra with a priority queue.
+func (d *directed[K, T]) ShortestPath(source, target T) ([]K, error) {
+	sourceHash := d.hash(source)
+	targetHash := d.hash(target)
+
+	return d.ShortestPathByHashes(sourceHash, targetHash)
+}
+
+func (d *directed[K, T]) ShortestPathByHashes(sourceHash, targetHash K) ([]K, error) {
+	weights := make(map[K]float64)
+	visited := make(map[K]bool)
+	predecessors := make(map[K]K)
+
+	weights[sourceHash] = 0
+	visited[sourceHash] = true
+
+	queue := newPriorityQueue[K]()
+
+	for hash := range d.vertices {
+		if hash != sourceHash {
+			weights[hash] = math.Inf(1)
+			visited[hash] = false
+		}
+
+		queue.Push(hash, weights[hash])
+	}
+
+	for queue.Len() > 0 {
+		vertex, _ := queue.Pop()
+		hasInfiniteWeight := math.IsInf(float64(weights[vertex]), 1)
+
+		if vertex == targetHash {
+			if _, ok := d.inEdges[vertex]; !ok {
+				return nil, fmt.Errorf("vertex %v is not reachable from vertex %v", targetHash, sourceHash)
+			}
+		}
+
+		outEdges, ok := d.outEdges[vertex]
+		if !ok {
+			continue
+		}
+
+		for successor, edge := range outEdges {
+			weight := weights[vertex] + float64(edge.Weight)
+
+			if weight < weights[successor] && !hasInfiniteWeight {
+				weights[successor] = weight
+				predecessors[successor] = vertex
+				queue.DecreasePriority(successor, weight)
+			}
+		}
+	}
+
+	// Backtrack the predecessors from target to source. These are the least-weighted edges.
+	path := []K{targetHash}
+	hashCursor := targetHash
+
+	for hashCursor != sourceHash {
+		hashCursor = predecessors[hashCursor]
+		path = append([]K{hashCursor}, path...)
+	}
+
+	return path, nil
+}
+
 func (d *directed[K, T]) edgesAreEqual(a, b Edge[T]) bool {
 	aSourceHash := d.hash(a.Source)
 	aTargetHash := d.hash(a.Target)
diff --git a/graph.go b/graph.go
index 8d4190c..7f27006 100644
--- a/graph.go
+++ b/graph.go
@@ -141,6 +141,19 @@ type Graph[K comparable, T any] interface {
 	//
 	// Note that the current implementation uses recursive function calls.
 	StronglyConnectedComponents() ([][]K, error)
+
+	// ShortestPath computes the shortest path between a source and a target vertex using the edge
+	// weights and returns the hash values of the vertices forming that path. This search runs in
+	// O(|V|+|E|log(|V|)) time.
+	//
+	// The returned path includes the source and target vertices. If the target cannot be reached
+	// from the source vertex, ShortestPath returns an error. If there are multiple shortest paths,
+	// an arbitrary one will be returned.
+	ShortestPath(source, target T) ([]K, error)
+
+	// ShortestPathByHashes does the same as ShortestPath, but uses hash values to identify the
+	// vertices.
+	ShortestPathByHashes(sourceHash, targetHash K) ([]K, error)
 }
 
 // Edge represents a graph edge with a source and target vertex as well as a weight, which has the
diff --git a/img/dijkstra.svg b/img/dijkstra.svg
new file mode 100644
index 0000000..e1912ba
--- /dev/null
+++ b/img/dijkstra.svg
@@ -0,0 +1,4 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!-- Do not edit this file with editors other than diagrams.net -->
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" version="1.1" width="353px" height="171px" viewBox="-0.5 -0.5 353 171" content="&lt;mxfile host=&quot;app.diagrams.net&quot; modified=&quot;2022-06-30T19:16:32.713Z&quot; agent=&quot;5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/102.0.0.0 Safari/537.36&quot; version=&quot;20.0.3&quot; etag=&quot;6sEl3GQaFPKViC0E3yXj&quot; type=&quot;device&quot;&gt;&lt;diagram id=&quot;1h-DLf8NitThQncVm08r&quot; name=&quot;Page-1&quot;&gt;7Vtdk5owFP01Pq5DSEB4XHV3O22306kP7T51WAlKC4RiXHV/fYMkAkbwY1GRYR92yA25kJOTk3sT7MCBv3yKrHD6TGzsdVTFXnbgsKOqOjLZ/9iwSgzQVBPDJHLtxARSw8h9x9yocOvctfEsdyMlxKNumDeOSRDgMc3ZrCgii/xtDvHyTw2tCZYMo7Hlydafrk2n3KoqSlrxCbuTqXi0Lmp8S9zNDbOpZZNFxgQfOnAQEUKTK385wF4MngAmafdYULt5swgH9JAGXxwS/nNQ8O3ZnPlvv8PpD+PznQoTN2+WN+ddvuevS1cCBOaH4c0K/cXUpXgUWuO4ZsFGnNmm1PdYCbBLaxYmg+C4S8we23dczxsQj0RrR9C2sOGMmX1GI/IXZ2r0sYFfHVbDXwdHFC8LOwo28DHeYeJjGq3YLbzBhjyccwjx8iIdQchN08zYCZvFOTPZeE5RZRcc2GNA1iSQBzcPci8PMjSvDbIugfxYIchngAxdHbKeBNnDrfMSwrpNfkMC+alevNxM3drw0pQgG9Ybsqurn3Ccgax/61MZaTWbylBex2WMA/s+jjtZKSABzuMakXlgx4AOlVLw/sz9cMR9ci8Ms2j1i7dcF16403VhuMxWDVeitHTpL3Efu37J2NMmcUG0KBrppKPYlsLlrdFkYJB5NMYHxJzUiiaY7o2bZH5kxl/bMf7CFmHPou5b/oV3kYI/4TtxWVfSOb61XGv6Fq+SjvJW2cB7yxFStxyBLUcJEJKjNUc33T6dtkiWUyjzlo3sV+uVZW95JfDcScCux2yUMeNEP57RLsuP7nmF79p27KMf4Zn7br2u/cVECuPurDuo9TvasEwSePLGG3c2GVOWXCUTslBAlK6iGCCHPfgYNcQtxHFm+CyDBeUwtjqNsbFjzT16jMIoJygMKFWYqyiJfk0lYStZV1d0XQE90OuZBjDy65oRExVC01ANRlpgwNN0RjVQF5oZP/mn6KCrgvQl1ItqkCbHJzt4fZMaVEAt7v5O6QJDvzURkhPDi4tQVzsl0OHNDgp1qhQivQ1pLionoLFy0tsX0iCRHn+QDFsNzqgm8g5IdWpyaNoETlKTWqVNvVZjLqoxqkRbMVS3rjHGHo0ByKx/jHJQVnvBTKn6vZirBCgF608rHsftucjnqpci5y6abaLi3UQrSP3TELyA0lUSVDuUoGZL0CpWN5mgqBmrWzL1ShNy9pcD/06t+2qHUKsnZ1rwCoKhVk+O0xN5y0hriJ6gUj2Jo2UxO2usH+c8umxcsGwcqB1Q2U2NVjuO0w55g6ghu3mo/IAyjkWg0Mkai8f1zySP2r6rUArEtyRtWnIhKZDj3IZsuqHyc0Klq6gon5XUPyk55zHhSd9D7U8xTkln6rS534Yc1eiMHA83JeQoP0BkIQfKIV/7jX50zuPDU76IOovGVKklh259tFpSjZbI4bHeEC0pPyhkWqKYdRETVkx/S5fcnv4iET78Bw==&lt;/diagram&gt;&lt;/mxfile&gt;" style="background-color: rgb(255, 255, 255);"><defs/><g><ellipse cx="19.5" cy="84.5" rx="19.5" ry="19.5" fill="#dae8fc" stroke="#6c8ebf" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 65px; margin-left: 1px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">A</div></div></div></foreignObject><text x="15" y="69" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">A</text></switch></g><ellipse cx="97.5" cy="19.5" rx="19.5" ry="19.5" fill="#dae8fc" stroke="#6c8ebf" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 15px; margin-left: 61px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">C</div></div></div></foreignObject><text x="75" y="19" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">C</text></switch></g><ellipse cx="97.5" cy="149.5" rx="19.5" ry="19.5" fill="rgb(255, 255, 255)" stroke="rgb(0, 0, 0)" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 115px; margin-left: 61px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">F</div></div></div></foreignObject><text x="75" y="119" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">F</text></switch></g><ellipse cx="175.5" cy="84.5" rx="19.5" ry="19.5" fill="#dae8fc" stroke="#6c8ebf" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 65px; margin-left: 121px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">E</div></div></div></foreignObject><text x="135" y="69" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">E</text></switch></g><ellipse cx="253.5" cy="149.5" rx="19.5" ry="19.5" fill="rgb(255, 255, 255)" stroke="rgb(0, 0, 0)" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 115px; margin-left: 181px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">G</div></div></div></foreignObject><text x="195" y="119" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">G</text></switch></g><ellipse cx="253.5" cy="19.5" rx="19.5" ry="19.5" fill="rgb(255, 255, 255)" stroke="rgb(0, 0, 0)" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 15px; margin-left: 181px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">D</div></div></div></foreignObject><text x="195" y="19" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">D</text></switch></g><ellipse cx="331.5" cy="84.5" rx="19.5" ry="19.5" fill="#dae8fc" stroke="#6c8ebf" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 65px; margin-left: 241px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">B</div></div></div></foreignObject><text x="255" y="69" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">B</text></switch></g><path d="M 33.29 70.71 L 83.71 33.29" fill="none" stroke="#6c8ebf" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 39px; margin-left: 45px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">3</div></div></div></foreignObject><text x="45" y="43" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">3</text></switch></g><path d="M 33.29 98.29 L 83.71 135.71" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 87px; margin-left: 42px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">2</div></div></div></foreignObject><text x="42" y="90" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">2</text></switch></g><path d="M 97.5 130 L 97.5 39" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 64px; margin-left: 76px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">2</div></div></div></foreignObject><text x="76" y="67" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">2</text></switch></g><path d="M 161.71 70.71 L 111.29 33.29" fill="none" stroke="#6c8ebf" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 38px; margin-left: 102px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">1</div></div></div></foreignObject><text x="102" y="41" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">1</text></switch></g><path d="M 111.29 135.71 L 161.71 98.29" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 90px; margin-left: 105px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">3</div></div></div></foreignObject><text x="105" y="93" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">3</text></switch></g><path d="M 117 19.5 L 234 19.5" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 17px; margin-left: 130px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">4</div></div></div></foreignObject><text x="130" y="21" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">4</text></switch></g><path d="M 117 149.5 L 234 149.5" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 115px; margin-left: 142px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">5</div></div></div></foreignObject><text x="142" y="119" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">5</text></switch></g><path d="M 267.29 135.71 L 317.71 98.29" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 92px; margin-left: 223px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">2</div></div></div></foreignObject><text x="223" y="95" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">2</text></switch></g><path d="M 316.24 72.36 L 267.29 33.29" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 42px; margin-left: 223px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">1</div></div></div></foreignObject><text x="223" y="45" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">1</text></switch></g><path d="M 195 84.5 L 312 84.5" fill="none" stroke="#6c8ebf" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 64px; margin-left: 177px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">2</div></div></div></foreignObject><text x="177" y="68" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">2</text></switch></g><path d="M 117 149.5 L 312 84.5" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 1px; height: 1px; padding-top: 92px; margin-left: 158px;"><div data-drawio-colors="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 11px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; background-color: rgb(255, 255, 255); white-space: nowrap;">6</div></div></div></foreignObject><text x="158" y="95" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="11px" text-anchor="middle">6</text></switch></g></g><switch><g requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"/><a transform="translate(0,-5)" xlink:href="https://www.diagrams.net/doc/faq/svg-export-text-problems" target="_blank"><text text-anchor="middle" font-size="10px" x="50%" y="100%">Text is not SVG - cannot display</text></a></switch></svg>
\ No newline at end of file
diff --git a/undirected.go b/undirected.go
index 2a84537..168bd96 100644
--- a/undirected.go
+++ b/undirected.go
@@ -3,6 +3,7 @@ package graph
 import (
 	"errors"
 	"fmt"
+	"math"
 )
 
 type undirected[K comparable, T any] struct {
@@ -262,6 +263,72 @@ func (u *undirected[K, T]) StronglyConnectedComponents() ([][]K, error) {
 	return nil, errors.New("strongly connected components may only be detected in directed graphs")
 }
 
+// ShortestPath computes the shortest path between two vertices and returns the hashes of the
+// vertices forming that path. The current implementation uses Dijkstra with a priority queue.
+func (u *undirected[K, T]) ShortestPath(source, target T) ([]K, error) {
+	sourceHash := u.hash(source)
+	targetHash := u.hash(target)
+
+	return u.ShortestPathByHashes(sourceHash, targetHash)
+}
+
+func (u *undirected[K, T]) ShortestPathByHashes(sourceHash, targetHash K) ([]K, error) {
+	weights := make(map[K]float64)
+	visited := make(map[K]bool)
+	predecessors := make(map[K]K)
+
+	weights[sourceHash] = 0
+	visited[sourceHash] = true
+
+	queue := newPriorityQueue[K]()
+
+	for hash := range u.vertices {
+		if hash != sourceHash {
+			weights[hash] = math.Inf(1)
+			visited[hash] = false
+		}
+
+		queue.Push(hash, weights[hash])
+	}
+
+	for queue.Len() > 0 {
+		vertex, _ := queue.Pop()
+		hasInfiniteWeight := math.IsInf(float64(weights[vertex]), 1)
+
+		if vertex == targetHash {
+			if _, ok := u.inEdges[vertex]; !ok {
+				return nil, fmt.Errorf("vertex %v is not reachable from vertex %v", targetHash, sourceHash)
+			}
+		}
+
+		inEdges, ok := u.inEdges[vertex]
+		if !ok {
+			continue
+		}
+
+		for successor, edge := range inEdges {
+			weight := weights[vertex] + float64(edge.Weight)
+
+			if weight < weights[successor] && !hasInfiniteWeight {
+				weights[successor] = weight
+				predecessors[successor] = vertex
+				queue.DecreasePriority(successor, weight)
+			}
+		}
+	}
+
+	// Backtrack the predecessors from target to source. These are the least-weighted edges.
+	path := []K{targetHash}
+	hashCursor := targetHash
+
+	for hashCursor != sourceHash {
+		hashCursor = predecessors[hashCursor]
+		path = append([]K{hashCursor}, path...)
+	}
+
+	return path, nil
+}
+
 func (u *undirected[K, T]) edgesAreEqual(a, b Edge[T]) bool {
 	aSourceHash := u.hash(a.Source)
 	aTargetHash := u.hash(a.Target)


Test patch:
diff --git a/collection_test.go b/collection_test.go
new file mode 100644
index 0000000..69060da
--- /dev/null
+++ b/collection_test.go
@@ -0,0 +1,269 @@
+package graph
+
+import (
+	"testing"
+)
+
+func TestPriorityQueue_Push(t *testing.T) {
+	tests := map[string]struct {
+		items                 []int
+		priorities            []float64
+		expectedPriorityItems []priorityItem[int]
+	}{
+		"queue with 5 elements": {
+			items:      []int{10, 20, 30, 40, 50},
+			priorities: []float64{6, 8, 2, 7, 5},
+			expectedPriorityItems: []priorityItem[int]{
+				{value: 20, priority: 8},
+				{value: 40, priority: 7},
+				{value: 10, priority: 6},
+				{value: 50, priority: 5},
+				{value: 30, priority: 2},
+			},
+		},
+	}
+
+	for name, test := range tests {
+		queue := newPriorityQueue[int]()
+
+		for i, item := range test.items {
+			queue.Push(item, test.priorities[i])
+		}
+
+		if len(queue.items) != len(test.expectedPriorityItems) {
+			t.Fatalf("%s: item length expectancy doesn't match: expected %v, got %v", name, len(test.expectedPriorityItems), len(queue.items))
+		}
+
+		for i, expectedPriorityItem := range test.expectedPriorityItems {
+			if queue.items[i] != expectedPriorityItem {
+				t.Errorf("%s: item doesn't match: expected %v at index %d, got %v", name, expectedPriorityItem, i, queue.items[i])
+			}
+		}
+	}
+}
+
+func TestPriorityQueue_Pop(t *testing.T) {
+	tests := map[string]struct {
+		items        []int
+		priorities   []float64
+		expectedItem int
+		shouldFail   bool
+	}{
+		"queue with 5 item": {
+			items:        []int{10, 20, 30, 40, 50},
+			priorities:   []float64{6, 8, 2, 7, 5},
+			expectedItem: 30,
+			shouldFail:   false,
+		},
+		"queue with 1 item": {
+			items:        []int{10},
+			priorities:   []float64{6},
+			expectedItem: 10,
+			shouldFail:   false,
+		},
+		"empty queue": {
+			items:      []int{},
+			priorities: []float64{},
+			shouldFail: true,
+		},
+	}
+
+	for name, test := range tests {
+		queue := newPriorityQueue[int]()
+
+		for i, item := range test.items {
+			queue.Push(item, test.priorities[i])
+		}
+
+		item, err := queue.Pop()
+
+		if test.shouldFail != (err != nil) {
+			t.Fatalf("%s: error expectancy doesn't match: expected %v, got %v (error: %v)", name, test.shouldFail, (err != nil), err)
+		}
+
+		if item != test.expectedItem {
+			t.Errorf("%s: item expectancy doesn't match: expected %v, got %v", name, test.expectedItem, item)
+		}
+	}
+}
+
+func TestPriorityQueue_DecreasePriority(t *testing.T) {
+	tests := map[string]struct {
+		items                 []priorityItem[int]
+		decreaseItem          int
+		decreasePriority      float64
+		expectedPriorityItems []priorityItem[int]
+	}{
+		"decrease 30 to priority 5": {
+			items: []priorityItem[int]{
+				{value: 40, priority: 40},
+				{value: 30, priority: 30},
+				{value: 20, priority: 20},
+				{value: 10, priority: 10},
+			},
+			decreaseItem:     30,
+			decreasePriority: 5,
+			expectedPriorityItems: []priorityItem[int]{
+				{value: 40, priority: 40},
+				{value: 20, priority: 20},
+				{value: 10, priority: 10},
+				{value: 30, priority: 5},
+			},
+		},
+		"decrease a non-existent item": {
+			items: []priorityItem[int]{
+				{value: 40, priority: 40},
+				{value: 30, priority: 30},
+				{value: 20, priority: 20},
+				{value: 10, priority: 10},
+			},
+			decreaseItem:     50,
+			decreasePriority: 10,
+			expectedPriorityItems: []priorityItem[int]{
+				{value: 40, priority: 40},
+				{value: 30, priority: 30},
+				{value: 20, priority: 20},
+				{value: 10, priority: 10},
+			},
+		},
+	}
+
+	for name, test := range tests {
+		queue := &priorityQueue[int]{
+			items: test.items,
+		}
+
+		queue.DecreasePriority(test.decreaseItem, test.decreasePriority)
+
+		if len(queue.items) != len(test.expectedPriorityItems) {
+			t.Fatalf("%s: item length expectancy doesn't match: expected %v, got %v", name, len(test.expectedPriorityItems), len(queue.items))
+		}
+
+		for i, expectedPriorityItem := range test.expectedPriorityItems {
+			if queue.items[i] != expectedPriorityItem {
+				t.Errorf("%s: item doesn't match: expected %v at index %d, got %v", name, expectedPriorityItem, i, queue.items[i])
+			}
+		}
+	}
+}
+
+func TestPriorityQueue_Len(t *testing.T) {
+	tests := map[string]struct {
+		items       []int
+		priorities  []float64
+		expectedLen int
+	}{
+		"queue with 5 item": {
+			items:       []int{10, 20, 30, 40, 50},
+			priorities:  []float64{6, 8, 2, 7, 5},
+			expectedLen: 5,
+		},
+		"queue with 1 item": {
+			items:       []int{10},
+			priorities:  []float64{6},
+			expectedLen: 1,
+		},
+		"empty queue": {
+			items:       []int{},
+			priorities:  []float64{},
+			expectedLen: 0,
+		},
+	}
+
+	for name, test := range tests {
+		queue := newPriorityQueue[int]()
+
+		for i, item := range test.items {
+			queue.Push(item, test.priorities[i])
+		}
+
+		len := queue.Len()
+
+		if len != test.expectedLen {
+			t.Errorf("%s: length expectancy doesn't match: expected %v, got %v", name, test.expectedLen, len)
+		}
+	}
+}
+
+func TestPriorityQueue_insertItemAt(t *testing.T) {
+	tests := map[string]struct {
+		items                 []priorityItem[int]
+		insertItem            int
+		insertPriority        float64
+		insertIndex           int
+		expectedPriorityItems []priorityItem[int]
+	}{
+		"insert in the middle of the queue": {
+			items: []priorityItem[int]{
+				{value: 10, priority: 10},
+				{value: 20, priority: 20},
+				{value: 30, priority: 30},
+				{value: 40, priority: 40},
+			},
+			insertItem:     25,
+			insertPriority: 25,
+			insertIndex:    2,
+			expectedPriorityItems: []priorityItem[int]{
+				{value: 10, priority: 10},
+				{value: 20, priority: 20},
+				{value: 25, priority: 25},
+				{value: 30, priority: 30},
+				{value: 40, priority: 40},
+			},
+		},
+		"insert at the start of the queue": {
+			items: []priorityItem[int]{
+				{value: 10, priority: 10},
+				{value: 20, priority: 20},
+				{value: 30, priority: 30},
+				{value: 40, priority: 40},
+			},
+			insertItem:     5,
+			insertPriority: 5,
+			insertIndex:    0,
+			expectedPriorityItems: []priorityItem[int]{
+				{value: 5, priority: 5},
+				{value: 10, priority: 10},
+				{value: 20, priority: 20},
+				{value: 30, priority: 30},
+				{value: 40, priority: 40},
+			},
+		},
+		"insert at the end of the queue": {
+			items: []priorityItem[int]{
+				{value: 10, priority: 10},
+				{value: 20, priority: 20},
+				{value: 30, priority: 30},
+				{value: 40, priority: 40},
+			},
+			insertItem:     50,
+			insertPriority: 50,
+			insertIndex:    4,
+			expectedPriorityItems: []priorityItem[int]{
+				{value: 10, priority: 10},
+				{value: 20, priority: 20},
+				{value: 30, priority: 30},
+				{value: 40, priority: 40},
+				{value: 50, priority: 50},
+			},
+		},
+	}
+
+	for name, test := range tests {
+		queue := &priorityQueue[int]{
+			items: test.items,
+		}
+
+		queue.insertItemAt(test.insertItem, test.insertPriority, test.insertIndex)
+
+		if len(queue.items) != len(test.expectedPriorityItems) {
+			t.Fatalf("%s: item length expectancy doesn't match: expected %v, got %v", name, len(test.expectedPriorityItems), len(queue.items))
+		}
+
+		for i, expectedPriorityItem := range test.expectedPriorityItems {
+			if queue.items[i] != expectedPriorityItem {
+				t.Errorf("%s: item doesn't match: expected %v at index %d, got %v", name, expectedPriorityItem, i, queue.items[i])
+			}
+		}
+	}
+}
diff --git a/directed_test.go b/directed_test.go
index 40494c2..e978563 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -521,6 +521,105 @@ func TestDirected_StronglyConnectedComponents(t *testing.T) {
 	}
 }
 
+func TestDirected_ShortesPath(t *testing.T) {
+	TestDirected_ShortestPathByHashes(t)
+}
+
+func TestDirected_ShortestPathByHashes(t *testing.T) {
+	tests := map[string]struct {
+		vertices             []string
+		edges                []Edge[string]
+		sourceHash           string
+		targetHash           string
+		expectedShortestPath []string
+		shouldFail           bool
+	}{
+		"graph as on img/dijkstra.svg": {
+			vertices: []string{"A", "B", "C", "D", "E", "F", "G"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "C", Weight: 3},
+				{Source: "A", Target: "F", Weight: 2},
+				{Source: "C", Target: "D", Weight: 4},
+				{Source: "C", Target: "E", Weight: 1},
+				{Source: "C", Target: "F", Weight: 2},
+				{Source: "D", Target: "B", Weight: 1},
+				{Source: "E", Target: "B", Weight: 2},
+				{Source: "E", Target: "F", Weight: 3},
+				{Source: "F", Target: "G", Weight: 5},
+				{Source: "G", Target: "B", Weight: 2},
+			},
+			sourceHash:           "A",
+			targetHash:           "B",
+			expectedShortestPath: []string{"A", "C", "E", "B"},
+		},
+		"diamond-shaped graph": {
+			vertices: []string{"A", "B", "C", "D"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "B", Weight: 2},
+				{Source: "A", Target: "C", Weight: 4},
+				{Source: "B", Target: "D", Weight: 2},
+				{Source: "C", Target: "D", Weight: 2},
+			},
+			sourceHash:           "A",
+			targetHash:           "D",
+			expectedShortestPath: []string{"A", "B", "D"},
+		},
+		"source equal to target": {
+			vertices: []string{"A", "B", "C", "D"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "B", Weight: 2},
+				{Source: "A", Target: "C", Weight: 4},
+				{Source: "B", Target: "D", Weight: 2},
+				{Source: "C", Target: "D", Weight: 2},
+			},
+			sourceHash:           "B",
+			targetHash:           "B",
+			expectedShortestPath: []string{"B"},
+		},
+		"target not reachable": {
+			vertices: []string{"A", "B", "C", "D"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "B", Weight: 2},
+				{Source: "A", Target: "C", Weight: 4},
+			},
+			sourceHash:           "A",
+			targetHash:           "D",
+			expectedShortestPath: []string{},
+			shouldFail:           true,
+		},
+	}
+
+	for name, test := range tests {
+		graph := newDirected(StringHash, &traits{})
+
+		for _, vertex := range test.vertices {
+			graph.Vertex(vertex)
+		}
+
+		for _, edge := range test.edges {
+			if err := graph.WeightedEdge(edge.Source, edge.Target, edge.Weight); err != nil {
+				t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+			}
+		}
+
+		shortestPath, err := graph.ShortestPathByHashes(test.sourceHash, test.targetHash)
+
+		if test.shouldFail != (err != nil) {
+			t.Fatalf("%s: error expectancy doesn't match: expected %v, got %v (error: %v)", name, test.shouldFail, (err != nil), err)
+		}
+
+		if len(shortestPath) != len(test.expectedShortestPath) {
+			t.Fatalf("%s: path length expectancy doesn't match: expected %v, got %v", name, len(test.expectedShortestPath), len(shortestPath))
+		}
+
+		for i, expectedVertex := range test.expectedShortestPath {
+			if shortestPath[i] != expectedVertex {
+				t.Errorf("%s: path vertex expectancy doesn't match: expected %v at index %d, got %v", name, expectedVertex, i, shortestPath[i])
+			}
+		}
+	}
+}
+
 func TestDirected_edgesAreEqual(t *testing.T) {
 	tests := map[string]struct {
 		a             Edge[int]
diff --git a/undirected_test.go b/undirected_test.go
index 11c038b..6d56d06 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -540,6 +540,105 @@ func TestUndirected_StronglyConnectedComponents(t *testing.T) {
 	}
 }
 
+func TestUndirected_ShortesPath(t *testing.T) {
+	TestUndirected_ShortestPathByHashes(t)
+}
+
+func TestUndirected_ShortestPathByHashes(t *testing.T) {
+	tests := map[string]struct {
+		vertices             []string
+		edges                []Edge[string]
+		sourceHash           string
+		targetHash           string
+		expectedShortestPath []string
+		shouldFail           bool
+	}{
+		"graph as on img/dijkstra.svg": {
+			vertices: []string{"A", "B", "C", "D", "E", "F", "G"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "C", Weight: 3},
+				{Source: "A", Target: "F", Weight: 2},
+				{Source: "C", Target: "D", Weight: 4},
+				{Source: "C", Target: "E", Weight: 1},
+				{Source: "C", Target: "F", Weight: 2},
+				{Source: "D", Target: "B", Weight: 1},
+				{Source: "E", Target: "B", Weight: 2},
+				{Source: "E", Target: "F", Weight: 3},
+				{Source: "F", Target: "G", Weight: 5},
+				{Source: "G", Target: "B", Weight: 2},
+			},
+			sourceHash:           "A",
+			targetHash:           "B",
+			expectedShortestPath: []string{"A", "C", "E", "B"},
+		},
+		"diamond-shaped graph": {
+			vertices: []string{"A", "B", "C", "D"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "B", Weight: 2},
+				{Source: "A", Target: "C", Weight: 4},
+				{Source: "B", Target: "D", Weight: 2},
+				{Source: "C", Target: "D", Weight: 2},
+			},
+			sourceHash:           "A",
+			targetHash:           "D",
+			expectedShortestPath: []string{"A", "B", "D"},
+		},
+		"source equal to target": {
+			vertices: []string{"A", "B", "C", "D"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "B", Weight: 2},
+				{Source: "A", Target: "C", Weight: 4},
+				{Source: "B", Target: "D", Weight: 2},
+				{Source: "C", Target: "D", Weight: 2},
+			},
+			sourceHash:           "B",
+			targetHash:           "B",
+			expectedShortestPath: []string{"B"},
+		},
+		"target not reachable": {
+			vertices: []string{"A", "B", "C", "D"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "B", Weight: 2},
+				{Source: "A", Target: "C", Weight: 4},
+			},
+			sourceHash:           "A",
+			targetHash:           "D",
+			expectedShortestPath: []string{},
+			shouldFail:           true,
+		},
+	}
+
+	for name, test := range tests {
+		graph := newUndirected(StringHash, &traits{})
+
+		for _, vertex := range test.vertices {
+			graph.Vertex(vertex)
+		}
+
+		for _, edge := range test.edges {
+			if err := graph.WeightedEdge(edge.Source, edge.Target, edge.Weight); err != nil {
+				t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+			}
+		}
+
+		shortestPath, err := graph.ShortestPathByHashes(test.sourceHash, test.targetHash)
+
+		if test.shouldFail != (err != nil) {
+			t.Fatalf("%s: error expectancy doesn't match: expected %v, got %v (error: %v)", name, test.shouldFail, (err != nil), err)
+		}
+
+		if len(shortestPath) != len(test.expectedShortestPath) {
+			t.Fatalf("%s: path length expectancy doesn't match: expected %v, got %v", name, len(test.expectedShortestPath), len(shortestPath))
+		}
+
+		for i, expectedVertex := range test.expectedShortestPath {
+			if shortestPath[i] != expectedVertex {
+				t.Errorf("%s: path vertex expectancy doesn't match: expected %v at index %d, got %v", name, expectedVertex, i, shortestPath[i])
+			}
+		}
+	}
+}
+
 func TestUndirected_edgesAreEqual(t *testing.T) {
 	tests := map[string]struct {
 		a             Edge[int]