Google Interview Question Software Developers
Country: United States
Dumbo Strategy. Not smart but does the job.
Suppose the graph has K pair of nodes, which are not connected.
We are not considering en.wikipedia.org/wiki/Multigraph.
In that case we need to add to these pairs all pairs having edge length more than 2.
Now, the problem becomes :
find_min ( start, end, [ original , modified_1, modified_2, ...modified_k ] )
That is, finding individual shortest path in the original graph, and then modifying the graph by joining the first pair and then continuing the same.
This surely solves the problem.
But let's take a look around this a bit more.
Suppose we do this :
find_min ( start, end, [ original_graph ] )
and find the path P.
Now, if we go through the path verices by vertices, edge by edge,
can we not calculate if replacing 3 of the verices by a 2 ( by inserting the virtual edge )
reduces the min value or not?
Thus, we may solve the problem by :
1. Finding min path
2. Check if directly connecting start to end solves it or not? If not, then proceed to [2]
3. For each 3 verices in 2 edges, we check if adding a virtual edge reduces the min or not.
4. Continue storing the previous min and go to [3].
Proof Of Correctness: NONE.
As of now, this can go wrong drastically.
Here is the idea (assuming positive integer weights):
1) If there exists an edge between source and destination go to (2) else return 1;
2) Use normal dijkstra's algorithm to find minimum distances to all the vertices from source and destination.
3) From the source distance array, for every vertex v1 (except source and vertex) in source distance array, see if for every vertex v2 (except source)
distance_source(v1) + distance_destination(v2) + 1 < distance_source(destination) if v1,v2 is not edge. Update the minimum source-destination distance.
4) Repeat for destination vertex. ie From the destination distance array, for every vertex v1 (except source and vertex) in destination distance array, see if for every vertex v2 (except destination)
distance_destination(v1) + distance_source(v2) + 1 < distance_source(destination) if v1,v2 is not edge. Update the minimum source-destination distance.
The idea is to calculate minimum distances of vertices from source and destination and then see if by adding an edge of weight 1, can we reduce source-destination distance.
/**
*
* Using BFS compute the weight of the shortest path from the starting vtx(s) to the
* destination vtx(e). Use a HashMap to keep track of which verticies have already been visited
* and update the minimum cost of reaching each vertex from s. For each vtx removed from the queue (t) check if it has a direct
* edge to e. If no direct edge exists, take the minimum cost of travelling to t(just do a lookup in the hash map) and add w to this value-
* this will be the minimum cost of going from t to e, update the hash map with the minimum cost
* of going to e from each vertex.
* Time: O(v + e) where v is the number of vertices and e is the number of edges.
* Space: O(v + e) due to hash map and bfs queue.
*
*
*
*/
private static class Edge
{
int vtx;
int cost;
}
public int minCost(List<Edge>[] adj, int w,int s, int e)
{
return minCostHelper(adj,w,s,e);
}
private int minCostHelper(List<Edge>[] adj, int w, int s, int e){
Map<Integer,Integer> lookUp = new HashMap<Integer,Integer>();
lookUp.put(s,0);
Deque<Integer> q = new LinkedList<Integer>();
q.addLast(s);
int minCost = Integer.MAX_VALUE;
while(!q.isEmpty()){
boolean hasDirect = false;
Integer top = q.pollFirst();
int initial = lookUp.get(top);
int cost;
for(Edge vtx:adj[top]){
cost = initial + vtx.cost;
if(!lookUp.containsKey(vtx.vtx) || cost < lookUp.get(vtx.vtx)){
if(!lookUp.containsKey(vtx.vtx)){
q.addLast(vtx.vtx);
}
lookUp.put(vtx.vtx,cost);
}
if(vtx.vtx == e){
hasDirect = true;
}
}
if(!hasDirect){
cost = initial + w;
if(!lookUp.containsKey(e) || cost < lookUp.get(e)){
lookUp.put(e,cost);
}
}
}
return lookUp.get(e);
}
}
/*
I solved it using dijkstra as in my previous post. I noticed how ever, the weight of the additional
edge is not 0 but 2 and that you may go over an intermediate node since the node you currently are
has a direct connection to end that is more expensive than when you would add the bonus-Edge to an
other node and go from there to the end.
So, again, I noticed how important it is to verify the steps before coding and getting into depth or
making wrong statements :-) The further I go with an error the more expensive to fix (in terms of
wasted time).
The key idea is to dynamically extend the graph to a graph g'. When ever we are on a vertex in
the original graph g, there are the edges given + to every other vertex where no edge was given
there exists the "bonus edge". Once used we are in g' and can't use the "bonus edge" anymore.
That is, im g' there exist only the original edges to vertices in g but to their "mirror" in
g'.
Visually, I drew the original graph g and on top a layer with the graph g'... Besides
this I could use dijkstra. A vertex is identified with an integer in this solution. A vertex
in g has an id below a certain value and a vertex in g' has just an offset to that id. There
are certainly more apealing designs to that, but it did work and I could verify some basic
cases.
*/
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <vector>
#include <iostream>
struct Edge
{
int destId_, weight_;
Edge(int destId, int weight) : destId_(destId), weight_(weight) { }
};
struct TraversalItem
{
int vertexId_, cost_, parentId_;
TraversalItem(int vertexId, int cost, int parentId)
: vertexId_(vertexId), cost_(cost), parentId_(parentId) { }
TraversalItem() : TraversalItem(-1, -1, -1) { }
};
using Path = std::pair<int, std::vector<std::pair<int, bool>>>;
class Graph
{
private:
const int bonusVertexIdOffset = 100000;
std::unordered_map<int, std::unordered_map<int, int>> edges_;
std::unordered_set<int> vertices_;
public:
void addEdge(int u, int v, int weight)
{
if (u >= bonusVertexIdOffset || v >= bonusVertexIdOffset) throw "id out of range";
edges_[u][v] = weight;
edges_[v][u] = weight;
addVertex(u);
addVertex(v);
}
void addVertex(int vertexId)
{
if (vertexId >= bonusVertexIdOffset || vertexId >= bonusVertexIdOffset) throw "id out of range";
vertices_.insert(vertexId);
}
// main part of algorithm
// it returns the path cost and the visited vertice id's with a flag wether they were in g or g'
Path getShortestPathWithBonusEdge(int start, int end, int bonusWeight)
{
auto tiComparer = [](const TraversalItem& a, const TraversalItem& b) -> bool { return a.cost_ > b.cost_; };
std::priority_queue<TraversalItem, std::vector<TraversalItem>, decltype(tiComparer) > tqueue(tiComparer);
std::unordered_map<int, TraversalItem> state;
tqueue.push(TraversalItem(start, 0, -1)); // start with start
state.emplace(std::pair<int, TraversalItem>(start, TraversalItem(start, 0, -1))); // start must be in state, too
while (tqueue.size() > 0)
{
auto u = tqueue.top();
tqueue.pop();
int uId = u.vertexId_;
if (uId == end || uId == end + bonusVertexIdOffset)
{
end = uId; // path end id, it might be in g'
break; // if end is now the cheapest to reach: done
}
auto edges = getOutEdges(uId, bonusWeight);
for (auto edge : edges)
{
int cost = u.cost_ + edge.weight_;
int vId = edge.destId_;
auto vStateIt = state.find(vId);
if (vStateIt == state.end())
{
TraversalItem ti(vId, cost, uId);
vStateIt = state.emplace(std::pair<int, TraversalItem>(vId, ti)).first;
tqueue.push(ti);
}
else if(vStateIt->second.cost_ > cost)
{
vStateIt->second.cost_ = cost;
vStateIt->second.parentId_ = uId;
tqueue.push(vStateIt->second); // since there's no update-key function...
}
}
}
// reconstruct path
auto stateIt = state.find(end);
if (stateIt != state.end())
{
// reached the end
std::vector<std::pair<int, bool>> path;
int vertexId = stateIt->second.vertexId_;
int cost = stateIt->second.cost_;
while (vertexId != -1)
{
bool gs = vertexId >= bonusVertexIdOffset;
int vId = gs ? vertexId - bonusVertexIdOffset : vertexId;
path.push_back(std::pair<int, bool>(vId, gs));
vertexId = state[vertexId].parentId_;
}
return Path(cost, std::vector<std::pair<int, bool>>(path.rbegin(), path.rend()));
}
return Path(-1, std::vector<std::pair<int, bool>>()); // empty path
}
private:
std::vector<Edge> getOutEdges(int vertexId, int bonusEdgeWeight)
{
std::vector<Edge> edges;
int u = vertexId;
int vIdOffset = 0;
if (u >= bonusVertexIdOffset)
{
u -= bonusVertexIdOffset;
// bonusedge already used, so only original edges are possible
auto edgeIt = edges_.find(u);
if (edgeIt != edges_.end())
{
for (auto v : edgeIt->second)
{
// use orginial edge but stay in g'
edges.push_back(Edge(v.first + bonusVertexIdOffset, v.second));
}
}
return edges;
}
// a vertex that was reaches without bonus edge, so
// every pair of edges is possible: either from the original
// graph or using the bonusEdge
for (auto v : vertices_)
{
if (v == u) continue;
auto edgeIt1 = edges_.find(u);
if (edgeIt1 != edges_.end())
{
auto edgeIt2 = edgeIt1->second.find(v);
if (edgeIt2 != edgeIt1->second.end())
{
// use original edge within g
edges.push_back(Edge(v, edgeIt2->second));
continue;
}
}
// add bonus edge to g'
edges.push_back(Edge(v + bonusVertexIdOffset, bonusEdgeWeight));
}
return edges;
}
};
void printResult(int start, int end, int bonusWeight, const Path& path)
{
std::cout << "shortes path from " << start << " to " << end
<< " with bonus edge weight " << bonusWeight << " is " << std::endl;
std::cout << " weight: " << path.first << std::endl;
std::cout << " path: ";
for (auto v : path.second)
{
std::cout << v.first << (v.second ? "' " : " ");
}
std::cout << std::endl << std::endl;
}
int main()
{
Graph g;
g.addEdge(1, 2, 2);
g.addEdge(1, 4, 4);
g.addEdge(2, 3, 1);
g.addEdge(3, 4, 3);
g.addEdge(4, 5, 1);
g.addEdge(5, 6, 8);
g.addEdge(3, 6, 9);
g.addEdge(1, 6, 99);
g.addEdge(2, 6, 99);
g.addVertex(20);
printResult(1, 5, 2, g.getShortestPathWithBonusEdge(1, 5, 2));
printResult(1, 4, 2, g.getShortestPathWithBonusEdge(1, 4, 2));
printResult(1, 5, 50, g.getShortestPathWithBonusEdge(1, 5, 50));
printResult(1, 6, 9, g.getShortestPathWithBonusEdge(1, 6, 9));
printResult(1, 6, 7, g.getShortestPathWithBonusEdge(1, 6, 7));
printResult(1, 20, 25, g.getShortestPathWithBonusEdge(1, 20, 25));
/* Output
shortes path from 1 to 5 with bonus edge weight 2 is
weight: 2
path: 1 5'
shortes path from 1 to 4 with bonus edge weight 2 is
weight: 3
path: 1 5' 4'
shortes path from 1 to 5 with bonus edge weight 50 is
weight: 5
path: 1 4 5
shortes path from 1 to 6 with bonus edge weight 9 is
weight: 12
path: 1 2 3 6
shortes path from 1 to 6 with bonus edge weight 7 is
weight: 11
path: 1 4 6'
shortes path from 1 to 20 with bonus edge weight 25 is
weight: 25
path: 1 20'
*/
}
from collections import defaultdict
class Graph(object):
def __init__(self, n):
self.nodes = range(1, n+1)
self.edges = defaultdict(list)
self.distances = dict()
for i in self.nodes:
for j in self.nodes:
self.edges[i].append(-j)
for i in self.nodes:
for j in self.nodes:
self.distances[(i,j)] = 2
def add_edge(self, u, v, dist):
self.edges[u][v-1] = -1*self.edges[u][v-1]
self.edges[v][u-1] = -1*self.edges[v][u-1]
self.distances[(u, v)] = dist
self.distances[(v, u)] = dist
def dijkstra(self, start, end):
unvisited = dict()
for node in self.nodes:
unvisited[node] = None
unvisited[-node] = None
visited = dict()
cur = start
dist = 0
unvisited[cur] = dist
while unvisited:
visited[cur] = unvisited[cur]
del unvisited[cur]
for nbor in self.edges[abs(cur)]:
if cur < 0:
if nbor < 0: continue
else: nbor = -nbor
if nbor in visited: continue
new_dist = dist + self.distances[(abs(cur), abs(nbor))]
if unvisited[nbor] == None \
or unvisited[nbor] > new_dist:
unvisited[nbor] = new_dist
if unvisited:
candidates = [node for node in unvisited.items() if node[1]]
candidates.sort(key=lambda k:k[1])
cur, dist = candidates[0]
return min(visited[end], visited[-end])
g = Graph(5)
g.add_edge(1, 2, 2)
g.add_edge(1, 4, 4)
g.add_edge(2, 3, 1)
g.add_edge(3, 4, 3)
g.add_edge(4, 5, 1)
print g.dijkstra(1, 4)
source: s, destination: t, extra vertex weight = wex
- tahini October 15, 2016My algorithm would be:
1. Compute all-pair shortest path
2. For all vertices k do:
globalmin = min(globalmin, min(d[s,t], d[s,k]+wex, d[k,t]+wex) )
In the second step, wex must be equal to infinity whenever s<->k (directly connected) and k<->t.