Google Interview! I heard back from them. Too late.
There is a typo in the title.
Write a code to find the shortest path in an undirected weighted graph where weights can be negative.
I immediately discerned the crux of the problem — that Dijsktra’s algorithm is not the way to go as it does not handle negatively weighted graphs. So I mentioned it to the interviewer. Thereafter, Bellman-Ford algorithm crossed my mind. Even though I knew that this algorithm is also devised for digraphs, I started implementing it, hoping that I can somehow manage it for undirected edges.
The initial implementation did not work for obvious reason.
No doubt that I was stressed out.
I started tweaking the graph by turning the undirected edges to directed one and modifying Bellman-Ford algorithm. The interviewer went through my algorithm and showed that it does not work. She was right! I found the bug but could not manage to solve it. Too disappointed at myself after the interview.
Right after the interview, I started reimplementing it and debugging this time using compiler yet I failed many times. Segfaults due to infinite loop popped up. After spending almost a half-day, I gave up and searched for the problem. Even finding a solution or an inkling was not easy. After a day of investigation, I found a related problem called “Chinese postman problem” where the concept of T-join was introduced in:
Took me a day to chew the problem and still have not digested it fully. I have
n̶o̶t̶ heard back from G**gle. Too late. Already have a job. Life is not just.
Choosing the right shortest path algorithm
Let me know if you find an error.
https://github.com/abbasinasab
