-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGraphMine.cs
More file actions
61 lines (51 loc) · 1.87 KB
/
Copy pathGraphMine.cs
File metadata and controls
61 lines (51 loc) · 1.87 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using System.Collections.Generic;
namespace CodingProblems
{
public class GraphMine
{
public Dictionary<string, Dictionary<string, int>> Vertices { get; set; }
public GraphMine()
{
Vertices = new Dictionary<string, Dictionary<string, int>>();
}
public void Add(string name, Dictionary<string, int> paths)
{
Vertices.Add(name, paths);
}
public int ShortestDistance(string origin, string destination)
{
MinHeap<GraphEdge<string>> minDistances = new MinHeap<GraphEdge<string>>();
var distances = new Dictionary<string, GraphEdge<string>>();
foreach (var node in Vertices)
{
var edge = new GraphEdge<string> { Node = node.Key, Distance = node.Key == origin ? 0 : int.MaxValue };
minDistances.Add(edge);
distances.Add(node.Key, edge);
}
while (minDistances.Length > 0)
{
var currentNode = minDistances.PopMin();
if (currentNode.Node == destination)
{
// Shortest path found
return currentNode.Distance;
}
if (currentNode.Distance == int.MaxValue)
{
// Impossible path
return int.MaxValue;
}
foreach (var adjacent in Vertices[currentNode.Node])
{
var newDistance = currentNode.Distance + adjacent.Value;
if (newDistance < distances[adjacent.Key].Distance)
{
distances[adjacent.Key].Distance = newDistance;
minDistances.Heapify();
}
}
}
return int.MaxValue;
}
}
}