Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Best way get the shortest path in an undirected graph with dp.

Revision en2, by BanazadehAria, 2019-06-07 14:56:39

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];
}
Tags #problem, #graph, #dynamic-programming

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)