why is the code not working properly for directed graph?
Dijkstra Algorithm Doubt
See this code:
I have also created comments where necessary so that you can understand it better.
#include<bits/stdc++.h>
#define moduli 998244353
#define int long long int
#define ld long double
#define F first
#define S second
#define P pair<int,int>
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define um unordered_map
#define R return
using namespace std;
template<typename T>
class Graph
{
unordered_map<T, list<pair<T, int>>> m;
public:
// Graph();
void addEdge(T u, T v, int dist, bool bidir = true) {
m[u].push_back(make_pair(v, dist));
if (bidir) {
m[v].pb(make_pair(u, dist));
}
}
void printAdj() {
for (auto j : m) {
cout << j.F << "---->";
for (auto k : j.S) {
cout << "(" << k.F << ", " << k.S << "), ";
}
cout << endl;
}
}
void dijkstra(T src) {
unordered_map<T, int> dist;
//Set all distances to infinity;
for (auto j : m) {
dist[j.F] = INT_MAX;
}
//Make a set to find out node with the minimum distance
set<pair<int, T>> s;
dist[src] = 0;
s.insert(make_pair(0, src));
while (!s.empty()) {
//Find the pair at the front
auto p = *(s.begin());
T node = p.S;
int nodeDistance = p.F;
s.erase(s.begin());
//Iterate over the neighbour of the current node
for (auto childPair : m[node]) {
if (nodeDistance + childPair.S < dist[childPair.F]) {
//In the set, updation is not possible,
//then we have to remove the old pair and insert the new pair
T dest = childPair.F;
auto f = s.find(make_pair(dist[dest], dest));
if (f != s.end()) {
s.erase(f);
}
//Insert the new pair
dist[dest] = nodeDistance + childPair.S;
s.insert(make_pair(dist[dest], dest));
}
}
}
//print distance
for (auto d : dist) {
cout << d.F << " is located at " << d.S << endl;
}
}
};
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base:: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// int t;cin>>t;while(t--)
{
int i, j, k, n, m, ans = 0, cnt = 0, sum = 0;
Graph<string> g;
cin >> n;
for (int i = 0; i < n; ++i)
{
string temp, temp1;
int temp2;
cin >> temp >> temp1 >> temp2;
g.addEdge(temp, temp1, temp2);
}
// g.printAdj();
g.dijkstra("Amritsar");
}
}
Thanks.
To run this you can any cities name, just making one of them as “Amritsar” is a must. because i started dijkstra from that. you can change that if you want.
(Note: Directed Graph)
for the above graph the answer has to be
distance from src to 2 is 1
distance from src to 5 is 2
distance from src to 4 is 7
distance from src to 3 is 2
distance from src to 1 is 0
but instead the output is coming
5 is located at 0
3 is located at 0
2 is located at 1
4 is located at 7
1 is located at 0
why??
because you implemented it wrong i think.
Are you talking about the code which i gave you??
yes your code was not giving right answer for the directed graph
6
1 2 1
1 3 4
1 4 7
2 3 1
4 3 2
1 5 2
i have set bool bidir to false so that the graph is directional
You modified the code wrongly.
See this.
/*
*-----------------------------------------------------------*
| |
| |
| AUTHOR: Himanshu Aswal |
| (himanshu010) |
| |
| |
*-----------------------------------------------------------*
*/
#include<bits/stdc++.h>
#define moduli 998244353
#define int long long int
#define ld long double
#define F first
#define S second
#define P pair<int,int>
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define um unordered_map
#define R return
using namespace std;
vector<vector<P>> graph(100005);
void addEdge(int u, int v, int dist) {
graph[u].pb({v, dist});
}
void printAdj(int n) {
for (int i = 0; i < n; ++i)
{
cout << i << "---->";
for (auto k : graph[i]) {
cout << "(" << k.F << ", " << k.S << "), ";
}
cout << endl;
}
}
void dijkstra(int src, int n) {
unordered_map<int, int> dist;
//Set all distances to infinity;
for (int i = 0; i < n; ++i)
{
dist[i] = INT_MAX;
}
//Make a set to find out node with the minimum distance
set<pair<int, int>> s;
dist[src] = 0;
s.insert({0, src});
while (!s.empty()) {
//Find the pair at the front
auto p = *(s.begin());
int node = p.S;
int nodeDistance = p.F;
s.erase(s.begin());
//Iterate over the neighbour of the current node
for (auto childPair : graph[node]) {
if (nodeDistance + childPair.S < dist[childPair.F]) {
//In the set, updation is not possible,
//then we have to remove the old pair and insert the new pair
int dest = childPair.F;
auto f = s.find({dist[dest], dest});
if (f != s.end()) {
s.erase(f);
}
//Insert the new pair
dist[dest] = nodeDistance + childPair.S;
s.insert({dist[dest], dest});
}
}
}
//print distance
for (auto d : dist) {
cout << d.F << " is located at " << d.S << endl;
}
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base:: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// int t;cin>>t;while(t--)
{
int i, j, k, n, m, ans = 0, cnt = 0, sum = 0;
cin >> n;
cin >> m;
for (int i = 0; i < m; ++i)
{
int temp, temp1;
int temp2;
cin >> temp >> temp1 >> temp2;
addEdge(temp, temp1, temp2);
}
// g.printAdj();
dijkstra(0, n);
}
}
changed the input format here for better grip over code and removed the class because i think that that thing is difficult to understand.
See input format:
first you have to give the number of vertices starting from zero(must start from zero and should be contiguous).
i.e. if vertices are 0,1,2,3,4. then the first line of input should contain 5 as there are five vertices.
then you have to give the number of edges.
and then the edges with weights.
input
5
7
0 1 1
0 2 4
0 3 7
1 2 1
3 2 2
0 4 2
4 3 1
output
4 is located at 2
3 is located at 3
2 is located at 2
0 is located at 0
1 is located at 1
Graph is very flexible and easy data structure, understand the basics and you can modify it in any way you want.
Thanks.
1 Like
thanks a lot man!!! truly appreciate your help
1 Like