Best way get the shortest path in an undirected graph with dp.
Difference between en1 and en2, changed 1 character(s)
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];↵
}↵
~~~~~↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English BanazadehAria 2019-06-07 14:56:39 1 Tiny change: 'han O(|V|)\n\n\n~~~~' -> 'han O(|V|)?\n\n\n~~~~'
en1 English BanazadehAria 2019-06-07 14:56:15 870 Initial revision (published)