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];
}