Search algorithms for graphs

[rabestro]

Story

As a user, I would like to find the shortest and the fastest routes in the graph. For the shortest path, the Bread First Search algorithm should be used. For the fastest path, we should use Dijkstra's algorithm.

Example

Given

Graph Schema

Vertex	Edges
A	[B:5, H:2]
B	[A:5, C:7]
C	[B:7, D:3, G:4]
D	[C: 20, E: 4]
E	[F: 5]
F	[G: 6]
G	[C: 4]
H	[G: 3]

When

we use the Breadth-First Search algorithm for the first route. and we use Dijkstra's algorithm for the second route.

Then

the first route is the shortest and the second route is the fastest

Where

The results for this graph are presented in the table

source	target	time	shortest	time	fastest
A	A	0	[A]	0	[A]
B	B	0	[B]	0	[B]
A	B	5	[A, B]	5	[A, B]
B	A	5	[B, A]	5	[B, A]
A	C	12	[A, B, C]	9	[A, H, G, C]
C	A	12	[C, B, A]	12	[C, B, A]
A	G	5	[A, H, G]	5	[A, H, G]
C	D	3	[C, D]	3	[C, D]
D	C	20	[D, C]	19	[D, E, F, G, C]
B	D	10	[B, C, D]	10	[B, C, D]
D	B	27	[D, C, B]	26	[D, E, F, G, C, B]
D	H	34	[D, C, B, A, H]	33	[D, E, F, G, C, B, A, H]

[rabestro]

Specifications: https://algorithms.jc.id.lv/docs/spock-reports/lv.id.jc.algorithm.graph.SearchAlgorithmsSpec.html