In java or C++ : Write a program that accepts any graph with up to 100 nodes (ca
ID: 3765770 • Letter: I
Question
In java or C++ :
Write a program that accepts any graph with up to 100 nodes (call them cities) and the distances between them (lengths of 2-ways roads between them) and returns the path with the shortest distance between any 2 cities (chosen by the user). Example: {(AB:10), (BD:5), (DC:11), (CA:6), (AD:17)} The path between A and D with the shortest distance is ABD:15. This is just one example; your program should be general. You may wish to pre-process some of the information provided in order to minimize the time complexity of the shortest path computation.
Explanation / Answer
Use Dijkstra's algorithm without the memory limitations imposed by a huge static allocated bi-dimensional array, allowing it to handle a large set of nodes. Djikstra is a very generic greedy algorithm and it's solution includes the worst case scenario: A graph where every node can be connected to all other nodes.
public class Dijkstra
{
private int _startNode = 0;
private List<destination> _nodes;
private Func<int, int, decimal> _values;
public int NumberOfNodes { get; private set; }
public bool IsSolved { get { return !_nodes.Any(n => !n.Done); } }
public Dijkstra(int numberOfNodes, Func<int, int, decimal> values)
{
if (numberOfNodes < 0) throw new ArgumentException("The number of nodes must be positive.");
if (values == null) throw new ArgumentNullException("values");
NumberOfNodes = numberOfNodes;
_values = values;
}
public void Reset()
{
if (_nodes == null) _nodes = new List<destination>();
_nodes.Clear();
for (var node = 0; node < NumberOfNodes; node++)
{
_nodes.Add(new Destination(node, node == _startNode));
var value = _values(_startNode, node);
if (value != -1) GetNode(node).AddStep(_startNode, value);
}
}
private Destination GetNode(int n)
{
return _nodes.SingleOrDefault(i => i.Node == n);
}
private void Iteraction()
{
var source = (from r in _nodes
where !r.Done
&& r.Path.Any()
orderby r.Path.Sum(p => p.Value)
select r).First();
var connectedNodes = (from r in _nodes
where r.Node != source.Node
&& r.Node != _startNode
&& _values(source.Node, r.Node) != -1
&& (!r.Path.Any() || r.Path.Sum(v => v.Value) > (source.Path.Sum(p => p.Value) + _values(source.Node, r.Node)))
select new { node = r, newValue = _values(source.Node, r.Node) }).ToList();
connectedNodes.ForEach(i => {
i.node.SetPath(source.Path);
i.node.AddStep(source.Node, i.newValue);
});
source.Done = true;
}
public IEnumerable<int> Solve(int startNode, int endNode)
{
if (startNode < 0 || startNode >= NumberOfNodes) throw new ArgumentException("The start node must be between zero and the number of nodes");
if (endNode < 0 || endNode >= NumberOfNodes) throw new ArgumentException("The end node must be between zero and the number of nodes");
_startNode = startNode;
Reset();
for (var i = 1; i < NumberOfNodes; i++) Iteraction();
GetNode(endNode).AddStep(endNode, 0);
return GetNode(endNode).Path.Select(p => p.Node);
}
private class Destination
{
public Destination(int n, bool d)
{
Node = n;
Path = new List<origin>();
Done = d;
}
public int Node { get; private set; }
public List<origin> Path { get; private set; }
public bool Done { get; internal set; }
public void AddStep(int d, decimal v)
{
Path.Add(new Origin(d, v));
}
public void SetPath(List<origin> p)
{
Path = new List<origin>(p);
}
}
private class Origin
{
public Origin(int n, decimal v)
{
Node = n;
Value = v;
}
public int Node { get; private set; }
public decimal Value { get; internal set; }
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.