_hopefullyme's blog

I need help in time complexity of this code.
By _hopefullyme, history, 4 months ago, In English 
// this code doesnt work unless you comment the lines 71-73 part...

// proof:
/*
input
5 5
1 2 1
2 3 1
3 4 1
4 5 1
1 5 1000
1

then input
5 5
1 5 1000
1 2 1
2 3 1
3 4 1
4 5 1
1

if you un-comment the lines, both output differently.
*/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) (v).begin(), (v).end()
#define endl '\n'

#define MOD 1000000007

ll mod(ll a) {
    return (a%MOD + MOD)%MOD;
}

ll binpow(ll x, ll n) {
    if (n == 0) {
        return 1;
    }
    if (x == 0) {
        return 0;
    }
    if (n%2 == 0) {
        ll temp = binpow(x,n/2);
        return mod(temp*temp);
    }
    return mod(mod(x)*binpow(x,n-1));
}

void print(bool& ans) { cout << (ans ? "YES" : "NO") << endl; }

// now we have weights(positive). Had weights were negative, we couldnot have used it.

#define f first
#define s second

vector<vector<pair<ll,ll>>> adj;
vector<ll> vis, dis;

void sssp(int src) {
    dis[src] = 0;
    queue<ll> q;
    q.push(src);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        // if (vis[node]) {    // the code works when you comment this part, because now for every time a node is pushed, it checks for distance.
        //     continue;
        // }
        vis[node] = 1;

        for (auto &x:adj[node]) {
            if (dis[x.f] > dis[node] + x.s) {
                dis[x.f] = dis[node] + x.s;
                q.push(x.f);
            }
        }
    }
}



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    adj = vector<vector<pair<ll,ll>>> (n+1);
    vis = vector<ll> (n+1,0);
    dis = vector<ll> (n+1,1e9);

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }

    int src;
    cin >> src;
    sssp(src);
    for (int i = 1; i <= n; i++) {
        cout << i << ": " << dis[i] << endl;
    }
    
    return 0;
}

WHAT IS THE TIME COMPLEXITY OF THIS APPROACH? IS THIS BETTER THAN OTHER SSSP ALGORITHMS?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You Can Use dijkstra algorithm for SSSP which Compelxity batter then Your code.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I understand, but what is the complexity of this code?

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Dijkstra Algorithm, Time Complexity : O(Elog(V)) and Your code is almost O(EV) time Complexity.

      → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It looks like you're trying to apply BFS-like traversal to a graph with weighted edges, which just doesn't work. You keep pushing nodes to the queue based on their proximity to the starting node, but with no respect to actual distances.

Just use Dijkstra's algorithm with something like a std::priority_queue.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is working if i am not marking them as visited (see commented line)

    → Reply