can someone to test or fix a bug in codding in C++ , i try to make the Dijkstra's Algorithm.cpp

[limber coral]

can someone to test or fix a bug in codding in C++ , i try to make the Dijkstra's Algorithm.cpp ( i made it but not sure if works fine ?

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1111
#define INF 999999999
vector< pair<int, int> >v[MAXN];

vector<int> djikstras(int source, int no_of_vertices) {
    vector<int> dist(no_of_vertices, INF);
    set< pair<int, int> > queue;
    vector<bool> visited(no_of_vertices, false);
    dist[source] = 0;
    visited[source] = true;
    queue.insert(make_pair(dist[source], source));

    while(!queue.empty()) {
        pair<int, int> front_p = *(queue.begin());
        queue.erase(queue.begin());
        int cur_dist = front_p.first;
        int node = front_p.second;

        for(int i=0; i<v[node].size(); i++) {
            int to = v[node][i].first;
            int weight = v[node][i].second;
            if(dist[to] > cur_dist + weight) {
                if(queue.find(make_pair(dist[to], to)) != queue.end()) {
                    queue.erase(make_pair(dist[to], to));
                }
                dist[to] = cur_dist + weight;
                queue.insert(make_pair(dist[to], to));
            }
        }    
    }
    return dist;
}

[quartz ivy]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[limber coral]

int main() {
    cout<<"\nEnter number of vertices\n";
    int no_of_vertices; cin >> no_of_vertices;

    cout<<"\nEnter number of edges\n";
    int no_of_edges; cin >> no_of_edges;

    /*
        Input the edges of undirected weighed graph  
        Format for input :
        vertex1 vertex2 weight
    */

    cout<<"\nUndirected weighted graph ";

    cout<<"\nEnter all edges one by one "
        <<"\nFormat for input : vertex1 vertex2 weight\n";
    for(int i=0; i<no_of_edges; i++) {
        int vertex1, vertex2, weight;
        cin >> vertex1 >> vertex2 >> weight;
        vertex1--, vertex2--;
        v[vertex1].push_back(make_pair(vertex2, weight));
        v[vertex2].push_back(make_pair(vertex1, weight));
    }

    /*
        Source vertex is that vertex from where shortest distance to all other vertices is to be found
    */
    
    cout<<"\nEnter the source vertex\n";
    int source; cin >> source;
    source --;
    vector<int> dist = djikstras(source, no_of_vertices);

    cout<<"\n";
    cout<<setw(10)<<"Source"<<setw(15)<<"Destination"<<setw(20)<<"Shortest Distance";
    cout<<"\n";
    for(int i=0; i<no_of_vertices; i++) {
        cout<<setw(10)<<source+1;
        cout <<setw(10)<<i + 1 <<setw(20)<< dist[i] << "\n";
    }
}

[icy tiger]

How do you mean you don't know if it works fine? Does it do what you expect it to do?

#define MAXN 1111
#define INF 999999999

also you realy shouldn't be using defines for this, just make them const variables or even better constexpr

using namespace std;
This is considered bad practice as well, while it's not blocking here you should consider just not doing that

#include<bits/stdc++.h>

That header however is a big no no, it's non standard and non portable making it impossible for a lot of people to even run your code, just include the proper headers your code should be using

[icy birch]

learning how to test your software is an important step in the learning process 🙂

in this case a good start would be to make some simple input that you can solve by hand to verify that your program is correct

[limber coral]

@icy tiger thanks i changed some code ...

[icy tiger]

so what part doesn't work of this?

[quartz ivy]

@limber coral Has your question been resolved? If so, type !solved :)

[limber coral]

@icy tiger the goal is

Implement Dijkstra's algorithm for finding the shortest paths in a directed graph (from a given node to all others).
Do not use Floyd's algorithm. The graph is given by a list of edges.

[icy tiger]

Okay and does it do that?

[icy birch]

@limber coral please keep to this server rather than DMing me

@icy tiger there is a command to display info about why you should send messages in public, right? do you know what it is called?

[icy tiger]

Not sure tbh

[honest thorn]

If I got a dollar for every competitive programming code that includes bits/stdc++.h I'd be fucking rich

[limber coral]

i made and new version that maybe its more close to the goal ? 🙂

[icy tiger]

Well does it do what it should do?

[limber coral]

yes maybe ?

[icy tiger]

Look the issue is you are just sending code with no clear way for us to help

it's up to you to verify the code does what it is supposed to do

if you have a specific issue thats is good but you don't

[icy birch]

!howto ask

[quartz ivy]

How to Ask a Programming Question

Anyone can ask a question in our programming channels. Following the guide Writing The Perfect Question is recommended.

What to Post

State your problem clearly and provide all necessary details:

• the relevant portion of your code, or all of it
• the expected output
• the actual output (or the full error)
  :trophy: Gold Standard: Minimal Reproducible Example

Where to Post

Provide the relevant code in the message, and format it nicely with a code block*. If it's too much for one message, you can upload it:

• Compiler Explorer for most C and C++ snippets
• OnlineGDB for interaction, debugging
  :no_entry: Do not post screenshots, let alone photos of your screen!

* Use /code if you don't know how to format code blocks

[honest thorn]

!pm

!dm

[willow coyote]

Some general comments on your code:

• Your Edge structure represents a directed weighted edge in your graph.
• create_adjacency_list assumes that all vertices are zero based and only supports directed graphs. If you intended your graph to be undirected, edges must be added in both directions. (two-way vs. one-way roads, so to speak).
• dijkstr() has the potential of integer overflow if distances[current_vertex] == INT_MAX as you then add edge_weight to it.
• Checking the output by hand from the graph provided appears to be generating correct results.

[limber coral]

@willow coyote Thanks I made some changes in the code

[quartz ivy]

@limber coral Has your question been resolved? If so, type !solved :)

[limber coral]

@willow coyote i made and 2nd version , are you sure its 100 % working ?

Implement Dijkstra's algorithm for finding the shortest paths in a directed graph (from a given node to all others).
Do not use Floyd's algorithm. The graph is given by a list of edges.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <iomanip>

using namespace std;

#define MAXN 1111
#define INF INT_MAX

vector<pair<int, int>> v[MAXN];

vector<int> dijkstra(int source, int no_of_vertices) {
    vector<int> dist(no_of_vertices, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[source] = 0;
    pq.push({ 0, source });

    while (!pq.empty()) {
        int cur_dist = pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if (cur_dist > dist[node]) {
            continue; // Оптимизация: ако вече сме намерили по-къс път, пропускаме
        }

        for (auto edge : v[node]) {
            int to = edge.first;
            int weight = edge.second;
            if (dist[to] > dist[node] + weight) {
                dist[to] = dist[node] + weight;
                pq.push({ dist[to], to });
            }
        }
    }
    return dist;
}

[quartz ivy]

@limber coral

It looks like you may have code formatting errors in your message

Note: Make sure to use back-ticks (`) and not quotes (')
Note: Make sure to specify a highlighting language, e.g. `cpp`, after the back-ticks

Markup

```cpp
int main() {}
```

Result

int main() {}

[limber coral]

int main() {
    cout << "\nEnter number of vertices\n";
    int no_of_vertices;
    cin >> no_of_vertices;

    cout << "\nEnter number of edges\n";
    int no_of_edges;
    cin >> no_of_edges;

    cout << "\nEnter all edges one by one "
        << "\nFormat for input : vertex1 vertex2 weight\n";
    for (int i = 0; i < no_of_edges; i++) {
        int vertex1, vertex2, weight;
        cin >> vertex1 >> vertex2 >> weight;
        vertex1--, vertex2--;
        v[vertex1].push_back({ vertex2, weight }); // За ориентиран граф, само една посока
        // v[vertex2].push_back({vertex1, weight}); // Ако е неориентиран, добавете и тази линия
    }

    cout << "\nEnter the source vertex\n";
    int source;
    cin >> source;
    source--;

    vector<int> dist = dijkstra(source, no_of_vertices);

    cout << "\n";
    cout << setw(10) << "Source" << setw(15) << "Destination" << setw(20) << "Shortest Distance";
    cout << "\n";
    for (int i = 0; i < no_of_vertices; i++) {
        cout << setw(10) << source + 1;
        cout << setw(10) << i + 1 << setw(20) << dist[i] << "\n";
    }

    return 0;
}

[quartz ivy]

Stf was warned
Reason: Me and Others have been trying to explain this multiple times to you now. Don't ask people to check if your code is working. Do that testing yourself. if you have specific questions / issues ask away but verifying if the code is working is your job

Case 5440

[limber coral]

i testd it and works , but with 6 numbers ,,, maybe i missed something and for that I ask more experianced developers ...

[icy tiger]

Then give that detail

Explain what you tried

Explain what is wrong

[limber coral]

I think is missing using priority_queue with greater<pii>, which is correct for min-heap.

also
The check if (curr_dist > dist[u]) continue; is important for the efficiency of the algorithm.

and other ,,.....that maybe some experianced developers will find if missing

[icy tiger]

Sorry but this doesn't mean shit

Please actually describe what you did, what the issue is

[quartz ivy]

How to Ask a Programming Question

Anyone can ask a question in our programming channels. Following the guide Writing The Perfect Question is recommended.

What to Post

State your problem clearly and provide all necessary details:

• the relevant portion of your code, or all of it
• the expected output
• the actual output (or the full error)
  :trophy: Gold Standard: Minimal Reproducible Example

Where to Post

Provide the relevant code in the message, and format it nicely with a code block*. If it's too much for one message, you can upload it:

• Compiler Explorer for most C and C++ snippets
• OnlineGDB for interaction, debugging
  :no_entry: Do not post screenshots, let alone photos of your screen!

* Use /code if you don't know how to format code blocks

[icy tiger]

please actually read this

[willow coyote]

I believe the question you may be trying to ask might be rephrased like this:

"I think my implementation might be missing priority_queue with greater<pii>, which is necessary for a min-heap. Also, I believe the check if (curr_dist > dist[u]) continue; is important for efficiency. Are there any other mistakes or improvements that experienced developers might notice?"

• So you seem concerned about using a mini-heap as priority_queue defaults to a max-heap by default. This is correctly implemented in the latest code you provided. This will ensure that the node with the smallest distance (weight) is processed first.
• You are also correctly making use of the curr_dist > dist[u] check. Without it you could process nodes with outdated distances (weights) slowing it down.
• You are also preallocating the adjacency graph which should help performance. It will however be at the cost of scalability and memory efficiency given you have a hard limit on the size of your graph regardless of the number actually needed.
• I don't like the use of a global v[MAXN]
• You are assuming without validation that vertices are 1-based indexing by blindly decrementing vertex1 and vertex2.
• You are not handling disconnected graphs. If a vertex is not reachable from source you will still print it's distance resulting in garbage results or INT_MAX. Additionally a self loop (vertex1 == vertex2) would be incorrectly processed.
• I suggest that you also test that weights are never negative which are not supported by Dijkstra.

[limber coral]

@willow coyote Thank you , if you need help in web development I will help you free 🙂

[quartz ivy]

@limber coral Has your question been resolved? If so, type !solved :)