disjkstras algorithm code example
Example: dijkstra algorithm
//djikstra's algorithm using a weighted graph (STL)
//code by Soumyadepp
//insta: @soumyadepp
//linkedinID: https://www.linkedin.com/in/soumyadeep-ghosh-90a1951b6/
using namespace std;
//to find the closest unvisited vertex from the source
//note that numbering of vertices starts from 1 here. Calculate accordingly
ll minDist(ll dist[], ll n, bool visited[])
{
ll min = INT_MAX;
ll minIndex = 0;
for (ll i = 1; i <= n; i++)
{
if (!visited[i] && dist[i] <= min)
{
min = dist[i];
minIndex = i;
}
}
return minIndex;
}
//djikstra's algorithm for single source shortest path
void djikstra(vector<pair<ll, ll>> *g, ll n, ll src)
{
bool visited[n + 1];
ll dist[n + 1];
for (ll i = 0; i <= n; i++)
{
dist[i] = INT_MAX;
visited[i] = false;
}
dist[src] = 0;
for (ll i = 0; i < n - 1; i++)
{
ll u = minDist(dist, n, visited);
visited[u] = true;
for (ll v = 0; v < g[u].size(); v++)
{
if (dist[u] + g[u][v].second < dist[g[u][v].first])
{
dist[g[u][v].first] = dist[u] + g[u][v].second;
}
}
}
cout << "VERTEX : DISTANCE" << endl;
for (ll i = 1; i <= n; i++)
{
if (dist[i] != INT_MAX)
cout << i << " " << dist[i] << endl;
else
cout << i << " "
<< "not reachable" << endl;
}
cout << endl;
}
int main()
{
//to store the adjacency list which also contains the weight
vector<pair<ll, ll>> *graph;
ll n, e, x, y, w, src;
cout << "Enter number of vertices and edges in the graph" << endl;
cin >> n >> e;
graph = new vector<pair<ll, ll>>[n + 1];
cout << "Enter edges and weight" << endl;
for (ll i = 0; i < e; i++)
{
cin >> x >> y >> w;
//checking for invalid edges and negative weights.
if (x <= 0 || y <= 0 || w <= 0)
{
cout << "Invalid parameters. Exiting" << endl;
exit(-1);
}
graph[x].push_back(make_pair(y, w));
graph[y].push_back(make_pair(x, w));
}
cout << "Enter source from which you want to find shortest paths" << endl;
cin >> src;
if (src >= 1 && src <= n)
djikstra(graph, n, src);
else
cout << "Please enter a valid vertex as the source" << endl;
return 0;
}
//time complexity : O(ElogV)
//space complexity: O(V)