Hi, What is the best way to get the shortest path from vertex a to b in a weighted undirected graph?
I have done this but can we do better than O(|V|)?
map<int,list<pair<int,int> > > adjList;
void addEdge(int u,int v,int weight){
adjList[u].pb(mp(v,weight));
adjList[v].pb(mp(u,weight));
}
void FindShortestPath(int u,int v){
int dp[n];
dp[u]=0;
map<int,bool> visited;
queue<int> q;q.push(u);visited[u]=true;
while(!q.empty()){
int now = q.front();q.pop();
for(auto neight : adjList[now]){
dp[neight.first] = min(dp[neight.first],dp[now]+neight.second);
if(!visited[neight.first]){
q.push(neight.first);visited[neight.first]=true;
}
}
}cout << dp[v];
}
Auto comment: topic has been updated by BanazadehAria (previous revision, new revision, compare).
As far as I know, the best way to get the shortest path in a graph with positive weight is Dijkstra, and the complexity is $$$O(n\log n)$$$
Oh no you don't. Let V be the vertex set and E be the edge set. Then complexity of dijkstra's shortest path algo is $$$O((|V|+|E|)log(|V|)) = O(|V^2|log(|V|))$$$
Can u please elaborate, how O((v+e)log(v)) = O(v*v*log(v))?LanceTheDragonTrainer, I think it should be v*log(v) or e*log(v).
it is $$$\mathcal{O}(E\cdot\log(V))$$$ but $$$E \in \mathcal{O}(V^2)$$$
You can actually do $$$O(|V|^2)$$$ if $$$|E|$$$ is large. In every vertex you find the closest just by iterating through all vertices, and forget about the priority queue.
Another option is using fibonacci heap instead of standard binary heap, which gives $$$O(|E| + |V|log|V|)$$$.
Your first point is true. But that is worse than the time complexity that I described in general because you have to make VERY dense graphs for your algo to be useful.
Also, while fibonacci heap can indeed speed up the runtime of dijkstra's algo, I think that it is a common understanding that dijkstra's algo uses binary heap.
Just like dicnic's algo, you can speed it up using LCT, capacity scaling and all, but we still stick with the one which is commonly taught in academia.
Even thought fibonacci heaps are theoretically faster, there constant factor is so big that in practice a binary heap is always faster (atleast this holds for real world road networks... but in my tests this also holds for other graphs).
can we do better than O(|V|)?
What are you talking about? Lol. Take any deterministic path finding/shortest path algo. We can always make it traverse the entire graph for ANY given graph. I am lazy to provide a proof but you can easily prove it by induction. Anyway, without going into further details, just consider the case where we have a line graph. Now set your source and destination to be the ends of the graph. Your algo has no choice but to traverse all vertices of the graph.
Thank you
Your algorithm is wrong.
the shortest path from 1 to 4 las length 3 but your algorithm will say its 5...
Oh can you say what is wrong in my algorithm?
You are using a queue instead of heap so you are not taking into considerations the weights. What you do, would work in unweighted graphs, because what you are really doing is BFS.
You set node u as "visited" the first time you visit it. But maybe in the future you will find a shortest path that pass through u and leads to a better solution for an other node v. So to fix your solution, you should include node "u" to the queue every time you find a shortest path to u. But this will lead to O(n^2), so this is why we use Dijkstra's algorithm with heap.
But maybe in the future you will find a shortest path that pass through u andleads to a better solution for the other node vHi I didn't understand why is that?If we can go to a better place from u at later times then at first we can go to because we are visiting all of the neighbors of u.
Username checks out