- Notifications
You must be signed in to change notification settings - Fork0
Open
Assignees
Description
Story
As a user, I would like to find theshortest and thefastest routes in the graph. For the shortest path, theBread First Search algorithm should be used. For the fastest path, we should useDijkstra'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] |