单源最短路径.cpp

贪婪算法合集,包括二分覆盖,单源最短路径,拓扑排序,机器调度问题

//单源最短路径

#include <iostream>
#include "awd.h"
using namespace std;

void print(int i, int s,int p[])//递归输出p[p[p..[i]...]
{
	if(p[i]!=s&&p[i]!=0)
	{
		cout<<p[i]<<"->";
		print(p[i],s,p);
	}
}

/*另外一种输出路径的方法：
void Path(int p[], int s, int i)
{//输出最短路径from i to s.
	if (i != s && !p[i])
	{//没有路径
		cout << "There is no path from vertex "
           << s << " to vertex " << i << endl;
      return;
	}
   //有路径
   cout << "Shortest path from vertex "
        << s << " to vertex " << i
        << " is the reverse of " << i;
   while (i != s)
   {
	   //p[p[p..[i]...]就是靠下面这句实现的，它没有用递归，但是也实现了输出
	   i = p[i];
	   cout << " " << i;
   }
   cout << endl;

}*/
void main(void)
{
   AdjacencyWDigraph<int> G(5);
   int dist[6], p[6];
   int n = 5;
   cout << "enter number of edges of 5 vertex digraph" << endl;
   int e, u, v, w;
   cin >> e;
   // input edges
   for (int i =1; i <= e; i++) {
      cout << "enter edge " << i << endl;
      cin >> u >> v >> w;
      G.Add(u,v,w);}

   cout << "The input graph is" << endl;
   G.Output();

   G.ShortestPaths(1, dist, p);

   cout << "dist[i] and p[i] are" << endl;
   for (i=1; i<=n; i++)
	   cout << dist[i] << ' '<<p[i]<<endl;
   cout<<"路径分别为:\n";
   for (i=1;i<=n;i++)
   {
	   cout<<i<<"->";
	   print(i,1,p);
	   cout<<'1'<<endl;
   }
}