SEGMENTATION FAULT

[denver2020]

I got segmentation fault with below code. any idea what is wrong here?

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

// This is used to trace all paths from source to destination
void trace_path(int c, vector<vector<int>> &parent, vector<string> &ans, map<pair<int,int>,int> &mp) {
    for(int p:parent[c]) {
        ans[mp[{p,c}]] = "YES";
        trace_path(p, parent, ans, mp);
    }
}


vector<string> solve(int n, vector<int> from, vector<int> to, vector<int> weigh) {
    vector<vector<pair<int,int>>> adj (n+1);    // Adjancency List of the graph
    vector<string> ans (from.size(), "NO");     // Final Answer
    priority_queue<pair<int, int>> q;           // Used as a min heap
    vector<int> dst (n+1, 1e9);                 // Stores minimum distance of every node from Souce
    vector<vector<int>> parent (n+1);
    map<pair<int,int>, int > mp;                // Map is used here
    int i, u, v, w;
    for(i=0; i<from.size(); i++) {
        adj[from[i]].push_back({to[i], weigh[i]});
        adj[to[i]].push_back({from[i], weigh[i]});
        mp[{from[i], to[i]}] = i;
        mp[{to[i], from[i]}] = i;
    }
    q.push({0, 1});
    dst[1] = 0;
    while(!q.empty()) {
        u = q.top().second;
        q.pop();
        for(auto t:adj[u]) {
            v = t.first;
            w = t.second;
            // Delete Previously stored Parents if node distance reduces
            if(dst[v]>dst[u]+w)
                parent[v].clear();
            if(dst[v]>=dst[u]+w) {
                dst[v] = dst[u]+w;
                parent[v].push_back(u);
                q.push({-dst[v], v});
            }
        }
    }
    trace_path(n, parent, ans, mp);
    return ans;
}

 

int main() {
           
 int n, m;
    vector<int> from, to, weigh;
    cin >> n >> m;
    from.resize(m);
    to.resize(m);
    weigh.resize(m);
    for(int i=0; i<m; i++)
        cin >> from[i] >> to[i] >> weigh[i];
    vector<string> ans = solve(n, from, to, weigh);
    for(string s:ans)
        cout << s << " ";
    return 0;
}

[denver2020]

below is the dump analysis info.

Reading symbols from Solution...done.
[New LWP 51539]
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Core was generated by `./Solution'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0 0x0000000000401dc4 in solve[abi:cxx11](int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >) (n=0, from=..., to=..., weigh=...)
at /usr/local/include/c++/8.3.0/bits/stl_iterator.h:966
966 operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
To enable execution of this file add
add-auto-load-safe-path /usr/local/lib64/libstdc++.so.6.0.25-gdb.py
line to your configuration file "//.gdbinit".
To completely disable this security protection add
set auto-load safe-path /
line to your configuration file "//.gdbinit".
For more information about this security protection see the
"Auto-loading safe path" section in the GDB manual. E.g., run from the shell:
info "(gdb)Auto-loading safe path"

[mbozzi]

What does the program do?

I need a description of the intended behavior and instructions to reproduce the mistake.

[denver2020]

I am finding out the minimum distance of every node from Source to Destination.

[TheIdeasMan]

What is the base case for the recursion in the trace_path function?

Edit:

How many items in q ?

You started using gdb but didn't carry on.

Do you need all those includes?

using namespace std; is a bad idea. Google it.

[lastchance]

Is this supposed to be Dijkstra's algorithm?

I guessed at input (route round a square):

4 4
0 1 3
1 3 4
3 2 5
2 0 6

and it produced the endearing output

NO NO NO NO

[denver2020]

Yes, i m trying to solve it using Dijkstra algo.

[lastchance]

Yes, i m trying to solve it using Dijkstra algo. 

What is your priority queue actually sorted on?

A node only has one parent (computational version of "parthenogenesis"!). So you should update that, not do a mass of deleting. When you finalise a node (by popping it off the priority queue) then you update the distance to any other node to which it has access. If one of those nodes needs its distance shortening then it is put in the priority queue.

You need to give us the input data that caused your crash. Also tell us what n and m actually mean. (m seems to be the number of weighted paths, but I don't know what n is.) Also, it's unclear whether this is a directed graph or not.

[TheIdeasMan]

This is looking more and more like a traffic generation topic, sorry to say - probably because of the one sentence replies (unhelpful) from the OP.

[denver2020]

I need to find all paths from source to destination for a undirected weighted graph.
I have used Dijkstra algorithm here , in addition used list of parents to store all the shortest paths as you can see in the code here.

[lastchance]

denver2020

- You haven't provided the input that elicited your crash. It didn't crash for mine. But it didn't output anything meaningful either.
- You haven't told us what the individual inputs represent.
- You haven't told us how you expect your code to work. (Link to your algorithm or methodology).

If you don't answer questions fully and give all the information asked for then it is difficult to give assistance. Above all, we need an input file.

A priority queue is a perfectly good way of using Dijkstra's algorithm. It needs to be sorted on the basis of distance from source.

I would start by getting rid of the completely unnecessary splurge of headers.

[denver2020]

Input (stdin)


[A,B,3] [B,C,5] [C,D,2]
A->D,10

Output has to be
A->B->C->D

[denver2020]

I dont see crash now, rather I got the below output.

YES YES NO NO YES YES YES

But this is not the desired output as per the above comments. It seems logical issue. Any suggestions would help here.

Input (stdin)


[A,B,3] [B,C,5] [C,D,2]
A->D,10

Output has to be
A->B->C->D

[denver2020]

I had modified the logic here. Below is the code, but not able to see any output, it hangs.

[code]

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstdio>
using namespace std;

class Node{
public:
int id;
unsigned int dist;
vector<pair<Node *, int>> adjacent;

Node(int id)
: id(id), dist(-1)
{ }
};

int main() {
int t;
scanf("%d", &t);

for (int i = 0; i < t; i++) {
int n, m;
scanf("%d %d", &n, &m);

Node** nodes = new Node*[n + 1];

for (int j = 1; j <= n; j++) {
nodes[j] = new Node(j);
}

for (int j = 0; j < m; j++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
Node *o = nodes[x];
Node *p = nodes[y];
o->adjacent.emplace_back(p, z);
p->adjacent.emplace_back(o, z);
}

int s;
scanf("%d", &s);
priority_queue<pair<int, Node*>> pq;

nodes[s]->distance = 0;
pq.push(make_pair(0, nodes[s]));

while (!pq.empty()) {
const auto d = pq.top().first;
const auto o = pq.top().second;
pq.pop();

if (d > o->distance) {
continue;
}

for (const auto &pair : o->adjacent) {
const auto p = pair.first;
const auto e = pair.second;
if (p->distance > d + e) {
p->distance = d + e;
pq.push(make_pair(d + e, p));
}
}
}

bool first = true;

for (int j = 1; j <= n; j++) {
if (j == s) {
continue;
}

cout << (first ? "" : " ") << (int)nodes[j]->distance;
first = false;
}

cout << endl;
}

return 0;
}


[\code]

[lastchance]

[A,B,3] [B,C,5] [C,D,2]
A->D,10

How on earth is that supposed to correspond to your input. To remind you:

    cin >> n >> m;
....
    for(int i=0; i<m; i++)
        cin >> from[i] >> to[i] >> weigh[i];

I dont see crash now

Magic! Depends on time of day!

Output has to be
A->B->C->D

rather I got the below output.
YES YES NO NO YES YES YES
But this is not the desired output as per the above comments.

Err ... anyone like to explain that to me.

[denver2020]

Its a logical problem here. I have modified the code now with new changes, see above.
Kindly review it.

Same as http://www.cplusplus.com/forum/general/277585/

[denver2020]

Input
[A,B,3] [A,C,7] [C,D,2] [B,C,5]
A->D,10

Output
A->C->D




Input (stdin)


[A,B,3] [B,C,5] [C,D,2]
A->D,10

Output has to be
A->B->C->D

[lastchance]

Try this one:

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <limits>
using namespace std;

using NodeType = char;

struct Edge
{
   NodeType dest;
   double wt;
};
bool operator < ( Edge a, Edge b ) { return a.dest < b.dest; }

using Graph  = map< NodeType, set<Edge> >;
using Relate = map< NodeType, NodeType >;

//======================================================================

void read( istream &in, Graph &graph, bool directed = false )
{
   graph.clear();
   NodeType a, b;
   double wt;
   while( in >> a >> b >> wt )
   {
      graph[a].insert( Edge{ b, wt } );
      if ( !directed ) graph[b].insert( Edge{ a, wt } );
   }
}

//======================================================================

void write( ostream &out, const Graph &graph, bool directed = false )
{
   for ( const auto &pr : graph )
   {
      for ( const Edge &edge : pr.second )
      {
         if ( directed || pr.first < edge.dest ) out << pr.first << '\t' << edge.dest << '\t' << edge.wt << '\n';
      }
   }
}

//======================================================================

void traceback( NodeType start, NodeType finish, Relate &parent )
{
   Relate child;
   for ( NodeType n = finish; n != start; n = parent[n] ) child[parent[n]] = n;

   cout << start;
   for ( NodeType n = start; n != finish; n = child[n] ) cout << " -> " << child[n];
   cout << '\n';
}

//======================================================================

double Dijkstra( Graph &graph, NodeType start, NodeType finish )
{
   const double LARGE = numeric_limits<double>::max();

   // Set all distances except that of start to infinity
   map<NodeType,double> dist;
   for ( auto n : graph ) dist[n.first] = LARGE;
   dist[start] = 0;

   Relate parent;                      // To hold the most recent parent of each node

   // Create a priority queue that will be sorted by distance from source
   auto further = [&]( NodeType a, NodeType b ){ return dist[a] > dist[b]; };
   priority_queue< NodeType, vector<NodeType>, decltype(further) > Q( further );

   // Push all nodes accessible from the start onto the queue
   for ( const Edge &edge : graph[start] )
   {
      parent[edge.dest] = start;
      dist[edge.dest] = edge.wt;
      Q.push( edge.dest );
   }   

   // Dijkstra: take the smallest distance amongst those so far accessible and
   // finalise it (i.e. pop it from the top of the queue).
   while( !Q.empty() )
   {
      NodeType n = Q.top();
      if ( n == finish )               // If at the target then stop
      {
         traceback( start, finish, parent );
         return dist[n];
      }
      else                             // Otherwise update any distances via this route
      {
         Q.pop();
         for ( const Edge &edge : graph[n] )
         {
            double test = dist[n] + edge.wt;
            if ( dist[edge.dest] > test )        // If we improve a distance, then push onto queue
            {
               dist[edge.dest] = test;
               parent[edge.dest] = n;
               Q.push(edge.dest);
            }
         }
      }
   }

   // If we get this far then the target is inaccessible
   return -1.0;
}

//======================================================================

int main()
{
   istringstream in( "A B 3 \n"
                     "A C 7 \n"
                     "C D 2 \n"
                     "B C 5 \n" );
// ifstream in( "graph.in" );
// istream &in = cin;
   char start = 'A', finish = 'D';

   Graph G;
   read( in, G );

   cout << "Graph:\n";
   write( cout, G );

   cout << "\nShortest path from " << start << " to " << finish << ":\n";
   double d = Dijkstra( G, start, finish );
   cout << "Distance: " << d << '\n';
}

Your model answer is wrong, BTW.

Graph:
A	B	3
A	C	7
B	C	5
C	D	2

Shortest path from A to D:
A -> C -> D
Distance: 9

[denver2020]

Hi lastchance

Thanks for your quick response and guidance.
I have run your code with my test cases and it fails.

Below is details for Test1.

Input (stdin)
[A,B,3] [B,C,5] [C,D,2]
A->D,10

Your Output (stdout)
Graph:
A B 3
B C 5
C D 2

Shortest path:
A -> B -> C -> D
10

Expected Output
A->B->C->D



Below is the details for Test2.

Input (stdin)
[A,B,3] [B,C,5] [C,D,2] [A,C,7]
A->D,10

Your Output (stdout)
Graph:
A B 3
B C 5
C D 2

Shortest path:
A -> B -> C -> D
10

Expected Output
A->C->D



Below is Test3.

Input (stdin)
[A,B,5] [A,C,2] [B,C,4] [B,D,6] [C,B,7]
A->C,10

Your Output (stdout)
Graph:
A B 3
B C 5
C D 2

Shortest path:
A -> B -> C -> D
10

Expected Output

E2



Below is Test4.

Input (stdin)
[E,M,4] [E,L,19] [P,M,2] [L,P,12] [P,Q,10] [Q,F,4] [Q,G,7] [F,A,3] [G,H,10] [H,A,3] [G,A,5] [F,L,7] [A,L,2]
H->E,25

Your Output (stdout)
Graph:
A B 3
B C 5
C D 2

Shortest path:
A -> B -> C -> D
10

Expected Output
H->A->L->P->M->E



Below is Test5.

Input (stdin)
[A,B,3] [A,C,2] [3,4,A] [!,@,2]
A->B,4

Your Output (stdout)
Graph:
A B 3
B C 5
C D 2

Shortest path:
A -> B -> C -> D
10

Expected Output
E1


Below is Test6.

Input (stdin)
[Q,F,2] [Q,G,1] [F,T,2] [G,T,12] [G,N,3] [F,R,1] [R,P,6] [T,N,13]
T->Z,30

Your Output (stdout)
Graph:
A B 3
B C 5
C D 2

Shortest path:
A -> B -> C -> D
10

Expected Output

E2


Below is Test7.

Input (stdin)
[A,B,5] [A,C,7] [B,C,1] [C,D,3] [A,D,8] [D,E,3]
A->E,10

Your Output (stdout)
Graph:
A B 3
B C 5
C D 2

Shortest path:
A -> B -> C -> D
10

Expected Output

E3

[denver2020]

Below are my combination of tests with both input and expected output.

Input1
[A,B,3] [B,C,5] [C,D,2]
A->D,10

Output1 has to be
A->B->C->D


Input2
[A,B,3] [A,C,7] [C,D,2] [B,C,5]
A->D,10

Output2
A->C->D


Input3
[A,B,5] [A,C,2] [B,C,4] [B,D,6]
[C,B,7]
A->C,10

Output3
E2

Here the last edge [C,B,7] is a re-definition (duplication) of previously defined edge [B,C,4]. Such duplication should results in logical input error.