dijkstra algorithm implementation java code example
Example: dijkstra algorithm
#include <bits/stdc++.h>
#define ll long long
using namespace std;
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;
}
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()
{
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;
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;
}