Skip to content

Commit 52180d5

Browse files
kolosovpetrokolosovpetro
authored
Add Dijkstra Algorithm (TheAlgorithms#278)
1 parent defa33d commit 52180d5

File tree

6 files changed

+383
-2
lines changed

6 files changed

+383
-2
lines changed

‎Algorithms.Tests/Algorithms.Tests.csproj

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,5 +23,4 @@
2323
<PackageReference Include="nunit" Version="3.12.0" />
2424
<PackageReference Include="NUnit3TestAdapter" Version="3.15.1" />
2525
</ItemGroup>
26-
2726
</Project>

‎Algorithms.Tests/Graph/Dijkstra/DijkstraTests.cs

Lines changed: 229 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,229 @@
1+
using System;
2+
using Algorithms.Graph.Dijkstra;
3+
using DataStructures.Graph;
4+
using FluentAssertions;
5+
using NUnit.Framework;
6+
7+
namespace Algorithms.Tests.Graph.Dijkstra
8+
{
9+
[TestFixture]
10+
public class DijkstraTests
11+
{
12+
[Test]
13+
public void DijkstraTest1_Success()
14+
{
15+
// here test case is from https://www.youtube.com/watch?v=pVfj6mxhdMw
16+
17+
var graph = new DirectedWeightedGraph<char>(5);
18+
var a = graph.AddVertex('A');
19+
var b = graph.AddVertex('B');
20+
var c = graph.AddVertex('C');
21+
var d = graph.AddVertex('D');
22+
var e = graph.AddVertex('E');
23+
24+
graph.AddEdge(a, b, 6);
25+
graph.AddEdge(b, a, 6);
26+
27+
graph.AddEdge(a, d, 1);
28+
graph.AddEdge(d, a, 1);
29+
30+
graph.AddEdge(d, e, 1);
31+
graph.AddEdge(e, d, 1);
32+
33+
graph.AddEdge(d, b, 2);
34+
graph.AddEdge(b, d, 2);
35+
36+
graph.AddEdge(e, b, 2);
37+
graph.AddEdge(b, e, 2);
38+
39+
graph.AddEdge(e, c, 5);
40+
graph.AddEdge(c, e, 5);
41+
42+
graph.AddEdge(c, b, 5);
43+
graph.AddEdge(b, c, 5);
44+
45+
var shortestPathList = DijkstraAlgorithm.GenerateShortestPath(graph, a);
46+
shortestPathList.Length.Should().Be(5);
47+
48+
shortestPathList[0].Vertex.Should().Be(a);
49+
shortestPathList[0].Distance.Should().Be(0);
50+
shortestPathList[0].PreviousVertex.Should().Be(a);
51+
shortestPathList[0].ToString().Should()
52+
.Be($"Vertex: {a} - Distance: {0} - Previous: {a}");
53+
54+
shortestPathList[1].Vertex.Should().Be(b);
55+
shortestPathList[1].Distance.Should().Be(3);
56+
shortestPathList[1].PreviousVertex.Should().Be(d);
57+
shortestPathList[1].ToString().Should()
58+
.Be($"Vertex: {b} - Distance: {3} - Previous: {d}");
59+
60+
shortestPathList[2].Vertex.Should().Be(c);
61+
shortestPathList[2].Distance.Should().Be(7);
62+
shortestPathList[2].PreviousVertex.Should().Be(e);
63+
shortestPathList[2].ToString().Should()
64+
.Be($"Vertex: {c} - Distance: {7} - Previous: {e}");
65+
66+
shortestPathList[3].Vertex.Should().Be(d);
67+
shortestPathList[3].Distance.Should().Be(1);
68+
shortestPathList[3].PreviousVertex.Should().Be(a);
69+
shortestPathList[3].ToString().Should()
70+
.Be($"Vertex: {d} - Distance: {1} - Previous: {a}");
71+
72+
shortestPathList[4].Vertex.Should().Be(e);
73+
shortestPathList[4].Distance.Should().Be(2);
74+
shortestPathList[4].PreviousVertex.Should().Be(d);
75+
shortestPathList[4].ToString().Should()
76+
.Be($"Vertex: {e} - Distance: {2} - Previous: {d}");
77+
}
78+
79+
[Test]
80+
public void DijkstraTest2_Success()
81+
{
82+
var graph = new DirectedWeightedGraph<char>(5);
83+
var a = graph.AddVertex('A');
84+
var b = graph.AddVertex('B');
85+
var c = graph.AddVertex('C');
86+
87+
graph.AddEdge(a, b, 1);
88+
graph.AddEdge(b, a, 1);
89+
90+
graph.AddEdge(b, c, 1);
91+
graph.AddEdge(c, b, 1);
92+
93+
graph.AddEdge(a, c, 3);
94+
graph.AddEdge(c, a, 3);
95+
96+
var shortestPathList = DijkstraAlgorithm.GenerateShortestPath(graph, a);
97+
98+
shortestPathList.Length.Should().Be(3);
99+
shortestPathList[0].Vertex.Should().Be(a);
100+
shortestPathList[0].Distance.Should().Be(0);
101+
shortestPathList[0].PreviousVertex.Should().Be(a);
102+
shortestPathList[0].ToString().Should()
103+
.Be($"Vertex: {a} - Distance: {0} - Previous: {a}");
104+
105+
shortestPathList[1].Vertex.Should().Be(b);
106+
shortestPathList[1].Distance.Should().Be(1);
107+
shortestPathList[1].PreviousVertex.Should().Be(a);
108+
shortestPathList[1].ToString().Should()
109+
.Be($"Vertex: {b} - Distance: {1} - Previous: {a}");
110+
111+
shortestPathList[2].Vertex.Should().Be(c);
112+
shortestPathList[2].Distance.Should().Be(2);
113+
shortestPathList[2].PreviousVertex.Should().Be(b);
114+
shortestPathList[2].ToString().Should()
115+
.Be($"Vertex: {c} - Distance: {2} - Previous: {b}");
116+
}
117+
118+
[Test]
119+
public void DijkstraTest3_Success()
120+
{
121+
var graph = new DirectedWeightedGraph<char>(5);
122+
var a = graph.AddVertex('A');
123+
var b = graph.AddVertex('B');
124+
var c = graph.AddVertex('C');
125+
126+
graph.AddEdge(a, b, 1);
127+
graph.AddEdge(b, a, 1);
128+
129+
graph.AddEdge(a, c, 3);
130+
graph.AddEdge(c, a, 3);
131+
132+
var shortestPathList = DijkstraAlgorithm.GenerateShortestPath(graph, a);
133+
134+
shortestPathList.Length.Should().Be(3);
135+
shortestPathList[0].Vertex.Should().Be(a);
136+
shortestPathList[0].Distance.Should().Be(0);
137+
shortestPathList[0].PreviousVertex.Should().Be(a);
138+
shortestPathList[0].ToString().Should()
139+
.Be($"Vertex: {a} - Distance: {0} - Previous: {a}");
140+
141+
shortestPathList[1].Vertex.Should().Be(b);
142+
shortestPathList[1].Distance.Should().Be(1);
143+
shortestPathList[1].PreviousVertex.Should().Be(a);
144+
shortestPathList[1].ToString().Should()
145+
.Be($"Vertex: {b} - Distance: {1} - Previous: {a}");
146+
147+
shortestPathList[2].Vertex.Should().Be(c);
148+
shortestPathList[2].Distance.Should().Be(3);
149+
shortestPathList[2].PreviousVertex.Should().Be(a);
150+
shortestPathList[2].ToString().Should()
151+
.Be($"Vertex: {c} - Distance: {3} - Previous: {a}");
152+
}
153+
154+
[Test]
155+
public void DijkstraTest4_Success()
156+
{
157+
var graph = new DirectedWeightedGraph<char>(5);
158+
var a = graph.AddVertex('A');
159+
var b = graph.AddVertex('B');
160+
var c = graph.AddVertex('C');
161+
var d = graph.AddVertex('D');
162+
163+
graph.AddEdge(a, b, 1);
164+
graph.AddEdge(b, a, 1);
165+
166+
graph.AddEdge(a, c, 3);
167+
graph.AddEdge(c, a, 3);
168+
169+
graph.AddEdge(c, d, 5);
170+
graph.AddEdge(d, c, 5);
171+
172+
var shortestPathList = DijkstraAlgorithm.GenerateShortestPath(graph, a);
173+
174+
shortestPathList.Length.Should().Be(4);
175+
shortestPathList[0].Vertex.Should().Be(a);
176+
shortestPathList[0].Distance.Should().Be(0);
177+
shortestPathList[0].PreviousVertex.Should().Be(a);
178+
shortestPathList[0].ToString().Should()
179+
.Be($"Vertex: {a} - Distance: {0} - Previous: {a}");
180+
181+
shortestPathList[1].Vertex.Should().Be(b);
182+
shortestPathList[1].Distance.Should().Be(1);
183+
shortestPathList[1].PreviousVertex.Should().Be(a);
184+
shortestPathList[1].ToString().Should()
185+
.Be($"Vertex: {b} - Distance: {1} - Previous: {a}");
186+
187+
shortestPathList[2].Vertex.Should().Be(c);
188+
shortestPathList[2].Distance.Should().Be(3);
189+
shortestPathList[2].PreviousVertex.Should().Be(a);
190+
shortestPathList[2].ToString().Should()
191+
.Be($"Vertex: {c} - Distance: {3} - Previous: {a}");
192+
193+
// Vertex D won't be visited in this dijkstra implementation which is valid only for cyclic graphs,
194+
// since it is necessary to backtrack all unvisited vertices and place them
195+
// to the priority queue, which is not implemented yet in this repository.
196+
// If algo goes to the next vertex with minimal distance and this vertex is leaf -- algorithm stops.
197+
shortestPathList[3].Vertex.Should().Be(d);
198+
shortestPathList[3].Distance.Should().Be(double.MaxValue);
199+
shortestPathList[3].PreviousVertex.Should().BeNull();
200+
shortestPathList[3].ToString().Should()
201+
.Be($"Vertex: {d} - Distance: {double.MaxValue} - Previous: {null}");
202+
}
203+
204+
[Test]
205+
public void DijkstraMethodTest_ShouldThrow_GraphIsNull()
206+
{
207+
var graph = new DirectedWeightedGraph<char>(5);
208+
var a = graph.AddVertex('A');
209+
210+
Func<DistanceModel<char>[]> action = () => DijkstraAlgorithm.GenerateShortestPath(null!, a);
211+
212+
action.Should().Throw<ArgumentNullException>()
213+
.WithMessage($"Value cannot be null. (Parameter '{nameof(graph)}')");
214+
}
215+
216+
[Test]
217+
public void DijkstraMethodTest_ShouldThrow_VertexDoesntBelongToGraph()
218+
{
219+
var graph = new DirectedWeightedGraph<char>(5);
220+
var startVertex = graph.AddVertex('A');
221+
222+
Func<DistanceModel<char>[]> action = () => DijkstraAlgorithm.GenerateShortestPath(
223+
new DirectedWeightedGraph<char>(5), startVertex);
224+
225+
action.Should().Throw<ArgumentNullException>()
226+
.WithMessage($"Value cannot be null. (Parameter '{nameof(graph)}')");
227+
}
228+
}
229+
}

‎Algorithms/Graph/Dijkstra/DijkstraAlgorithm.cs

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using DataStructures.Graph;
5+
6+
namespace Algorithms.Graph.Dijkstra
7+
{
8+
public static class DijkstraAlgorithm
9+
{
10+
/// <summary>
11+
/// Implementation of the Dijkstra shortest path algorithm for cyclic graphs.
12+
/// https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.
13+
/// </summary>
14+
/// <param name="graph">Graph instance.</param>
15+
/// <param name="startVertex">Starting vertex instance.</param>
16+
/// <typeparam name="T">Generic Parameter.</typeparam>
17+
/// <returns>List of distances from current vertex to all other vertices.</returns>
18+
/// <exception cref="InvalidOperationException">Exception thrown in case when graph is null or start
19+
/// vertex does not belong to graph instance.</exception>
20+
public static DistanceModel<T>[] GenerateShortestPath<T>(DirectedWeightedGraph<T> graph, Vertex<T> startVertex)
21+
{
22+
ValidateGraphAndStartVertex(graph, startVertex);
23+
24+
var visitedVertices = new List<Vertex<T>>();
25+
26+
var distanceArray = InitializeDistanceArray(graph, startVertex);
27+
28+
var currentVertex = startVertex;
29+
30+
var currentPath = 0d;
31+
32+
while (true)
33+
{
34+
visitedVertices.Add(currentVertex);
35+
36+
var neighborVertices = graph
37+
.GetNeighbors(currentVertex)
38+
.Where(x => x != null && !visitedVertices.Contains(x))
39+
.ToList();
40+
41+
foreach (var vertex in neighborVertices)
42+
{
43+
var adjacentDistance = graph.AdjacentDistance(currentVertex, vertex!);
44+
45+
var distance = distanceArray[vertex!.Index];
46+
47+
if (distance.Distance <= currentPath + adjacentDistance)
48+
{
49+
continue;
50+
}
51+
52+
distance.Distance = currentPath + adjacentDistance;
53+
distance.PreviousVertex = currentVertex;
54+
}
55+
56+
var minimalAdjacentVertex = GetMinimalUnvisitedAdjacentVertex(graph, currentVertex, neighborVertices);
57+
58+
if (neighborVertices.Count == 0 || minimalAdjacentVertex is null)
59+
{
60+
break;
61+
}
62+
63+
currentPath += graph.AdjacentDistance(currentVertex, minimalAdjacentVertex);
64+
65+
currentVertex = minimalAdjacentVertex;
66+
}
67+
68+
return distanceArray;
69+
}
70+
71+
private static DistanceModel<T>[] InitializeDistanceArray<T>(
72+
IDirectedWeightedGraph<T> graph,
73+
Vertex<T> startVertex)
74+
{
75+
var distArray = new DistanceModel<T>[graph.Count];
76+
77+
distArray[startVertex.Index] = new DistanceModel<T>(startVertex, startVertex, 0);
78+
79+
foreach (var vertex in graph.Vertices.Where(x => x != null && !x.Equals(startVertex)))
80+
{
81+
distArray[vertex!.Index] = new DistanceModel<T>(vertex, null, double.MaxValue);
82+
}
83+
84+
return distArray;
85+
}
86+
87+
private static void ValidateGraphAndStartVertex<T>(DirectedWeightedGraph<T> graph, Vertex<T> startVertex)
88+
{
89+
if (graph is null)
90+
{
91+
throw new ArgumentNullException(nameof(graph));
92+
}
93+
94+
if (startVertex.Graph != null && !startVertex.Graph.Equals(graph))
95+
{
96+
throw new ArgumentNullException(nameof(graph));
97+
}
98+
}
99+
100+
private static Vertex<T>? GetMinimalUnvisitedAdjacentVertex<T>(
101+
IDirectedWeightedGraph<T> graph,
102+
Vertex<T> startVertex,
103+
IEnumerable<Vertex<T>?> adjacentVertices)
104+
{
105+
var minDistance = double.MaxValue;
106+
Vertex<T>? minVertex = default;
107+
108+
foreach (var vertex in adjacentVertices)
109+
{
110+
var currentDistance = graph.AdjacentDistance(startVertex, vertex!);
111+
112+
if (minDistance <= currentDistance)
113+
{
114+
continue;
115+
}
116+
117+
minDistance = currentDistance;
118+
minVertex = vertex;
119+
}
120+
121+
return minVertex;
122+
}
123+
}
124+
}

‎Algorithms/Graph/Dijkstra/DistanceModel.cs

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
using DataStructures.Graph;
2+
3+
namespace Algorithms.Graph.Dijkstra
4+
{
5+
/// <summary>
6+
/// Entity which represents the Dijkstra shortest distance.
7+
/// Contains: Vertex, Previous Vertex and minimal distance from start vertex.
8+
/// </summary>
9+
/// <typeparam name="T">Generic parameter.</typeparam>
10+
public class DistanceModel<T>
11+
{
12+
public Vertex<T>? Vertex { get; }
13+
14+
public Vertex<T>? PreviousVertex { get; set; }
15+
16+
public double Distance { get; set; }
17+
18+
public DistanceModel(Vertex<T>? vertex, Vertex<T>? previousVertex, double distance)
19+
{
20+
Vertex = vertex;
21+
PreviousVertex = previousVertex;
22+
Distance = distance;
23+
}
24+
25+
public override string ToString() =>
26+
$"Vertex: {Vertex} - Distance: {Distance} - Previous: {PreviousVertex}";
27+
}
28+
}

‎DataStructures/Graph/DirectedWeightedGraph.cs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
using System;
1+
using System;
22
using System.Collections.Generic;
33

44
namespace DataStructures.Graph

0 commit comments

Comments
 (0)