CareerCup

I am not sure this optimal or not,
1) we can construct graph from list of routes
2) then use Dijkstra's algorithm when he hit end, we stop the algorithm as Dikstra's gives shortest distance from start to all vertices but we just need till end here,
May be there is much easier way than what I wrote here :)

// Shortest-FlightRoute.cpp : Defines the entry point for the console application.
//Framed the graph with city names. added all the edges with time as the weigth of the edge.
//starting from the starting source city, run dfs. it will compute shorts paths to all destinations
//then return the shortest path to the destination city

#include "stdafx.h"
#include <unordered_map>
#include <vector>
#include <string>
#include <queue>

using namespace std;
struct dstwt
{
string point;
int time;
};
class Graph
{
vector<string> destinations;
unordered_map<string, vector<dstwt>> adj;
public:
Graph(const vector<string>& destinations);
void AddEdge(string src, string dst, int time);
int SP(string src, string dst);
};

Graph::Graph(const vector<string>& dests)
{
for (auto dest : dests)
destinations.push_back(dest);
}

void Graph::AddEdge(string src, string dst, int time)
{
auto entry = adj.find(src);
if (entry == adj.end())
{
adj[src] = { {dst,time} };
}
else
{
adj[src].push_back({ dst,time });
}

entry = adj.find(dst);
if (entry == adj.end())
{
adj[dst] = { { src,time } };
}
else
{
adj[dst].push_back({ src,time });
}
}

int Graph::SP(string src, string dst)
{
unordered_map<string, dstwt> distances;
for (auto dest : destinations)
{
distances[dest] = { {},9999 };
}
//set the starting point as 0
distances[src] = { {},0 };

auto comparefn = [](const dstwt& lhs, const dstwt& rhs) {return lhs.time > rhs.time; };

priority_queue<dstwt, vector<dstwt>, decltype(comparefn)> min_heap(comparefn);
min_heap.push({ src,0 });

while (!min_heap.empty())
{
auto u = min_heap.top();
min_heap.pop();
for (auto c : adj[u.point])
{
string v = c.point;
int time = c.time;
if (distances[v].time > distances[u.point].time + time)
{
distances[v].time = distances[u.point].time + time;
min_heap.push({ v,distances[u.point].time + time });
}
}
}

return distances[dst].time;

}


int main()
{
Graph g({ "sea","sfo","la","ord","nyc","dfw" });
g.AddEdge("sea", "sfo", 5);
g.AddEdge("sfo", "la", 10);
g.AddEdge("la", "ord", 15);
g.AddEdge("ord", "nyc", 3);
g.AddEdge("nyc", "dfw", 2);
g.AddEdge("sea", "dfw", 1);
int result = g.SP("sea", "ord");
return 0;
}

// Shortest-FlightRoute.cpp : Defines the entry point for the console application.
//Framed the graph with city names. added all the edges with time as the weigth of the edge.
//starting from the starting source city, run dfs. it will compute shorts paths to all destinations
//then return the shortest path to the destination city

#include "stdafx.h"
#include <unordered_map>
#include <vector>
#include <string>
#include <queue>

using namespace std;
struct dstwt
{
	string point;
	int time;
};
class Graph
{
	vector<string> destinations;
	unordered_map<string, vector<dstwt>> adj;
public:
	Graph(const vector<string>& destinations);
	void AddEdge(string src, string dst, int time);
	int SP(string src, string dst);
};

Graph::Graph(const vector<string>& dests)
{
	for (auto dest : dests)
		destinations.push_back(dest);
}

void Graph::AddEdge(string src, string dst, int time)
{
	auto entry = adj.find(src);
	if (entry == adj.end())
	{
		adj[src] = { {dst,time} };
	}
	else
	{
		adj[src].push_back({ dst,time });
	}

	entry = adj.find(dst);
	if (entry == adj.end())
	{
		adj[dst] = { { src,time } };
	}
	else
	{
		adj[dst].push_back({ src,time });
	}
}

int Graph::SP(string src, string dst)
{
	unordered_map<string, dstwt> distances;
	for (auto dest : destinations)
	{
		distances[dest] = { {},9999 };
	}
	//set the starting point as 0
	distances[src] = { {},0 };

	auto comparefn = [](const dstwt& lhs, const dstwt& rhs) {return lhs.time > rhs.time; };

	priority_queue<dstwt, vector<dstwt>, decltype(comparefn)> min_heap(comparefn);
	min_heap.push({ src,0 });

	while (!min_heap.empty())
	{
		auto u = min_heap.top();
		min_heap.pop();
		for (auto c : adj[u.point])
		{
			string v = c.point;
			int time = c.time;
			if (distances[v].time > distances[u.point].time + time)
			{
				distances[v].time = distances[u.point].time + time;
				min_heap.push({ v,distances[u.point].time + time });
			}
		}
	}

	return distances[dst].time;

}


int main()
{
	Graph g({ "sea","sfo","la","ord","nyc","dfw" });
	g.AddEdge("sea", "sfo", 5);
	g.AddEdge("sfo", "la", 10);
	g.AddEdge("la", "ord", 15);
	g.AddEdge("ord", "nyc", 3);
	g.AddEdge("nyc", "dfw", 2);
	g.AddEdge("sea", "dfw", 1);
	int result = g.SP("sea", "ord");
    return 0;
}

function findShortestPath(start, end, routes)
{
 	getRoutesFrom = function(start)
  {
    return this.routes.filter(function(item){ return (item.from == start)});
  };
	this.VisitedRoutes = [];
  this.routes = routes;
  this.allRoutes = [];
  findRoute = function(routeSoFar, totalTime, currentPlace, destination)
  {
  	var localRoutes = routeSoFar.slice();
    localRoutes.push(currentPlace);
    this.VisitedRoutes.push(currentPlace);
  	if (currentPlace==destination)
      this.allRoutes.push({'Path': localRoutes, 'timeTaken': totalTime});
    else
    {
      var outgoingRoutes = getRoutesFrom(currentPlace);
      for(var i=0; i<outgoingRoutes.length; i++)
      {
        	if (VisitedRoutes.indexOf(outgoingRoutes[i].end) < 0)
          	 findRoute(localRoutes, totalTime+outgoingRoutes[i].time, outgoingRoutes[i].to,destination);
      }
    }
  }
  
  findRoute([],0,start,end);
  this.allRoutes.sort(function(a,b){return (a.timeTaken - b.timeTaken)});
  console.log(this.allRoutes[0]);
}

findShortestPath('A','Z', [{from: 'A', to: 'B', time:24},{from: 'A', to: 'C', time:31},{from: 'B', to: 'Z', time:5},{from: 'C', to: 'D', time:15},{from: 'D', to: 'E', time:21},{from: 'E', to: 'Z', time:10}, {from: 'A', to: 'D', time:6}, {from: 'D', to: 'B', time:9}])