Function shortestPathDAG

CPP/graphseries.cpp:280–317

shortest path in weighted DAG(Directed Acyclic Graph)

// shortest path in weighted DAG(Directed Acyclic Graph)
void shortestPathDAG(vector<pair<int, int>> arr[], int n, int source)
{
	stack<int> s;
	vector<int> vis(n, 0);
	for (int i = 0; i < n; i++)
	{
		if (!vis[i])
		{
			findTopoSortDFS2(i, arr, s, vis);
		}
	}

	vector<int> distance(n, INT_MAX);
	distance[source] = 0;
	while (!s.empty())
	{
		int temp = s.top();
		s.pop();

		if (distance[temp] != INT_MAX)
		{
			for (auto i : arr[temp])
			{
				distance[i.first] = min(distance[i.first], distance[temp] + i.second);
			}
		}
	}

	for (auto i : distance)
	{
		if (i == INT_MAX)
		{
			cout << "This node is not reachable";
		}
		else
			cout << i << " ";
	}
}

//shortest path in weighted undirected graph
void dijkstrasAlgorithm(vector<int,int>arr[],int n,int source){