shortestpathwithstl.cpp

使用STL实现搜索链表的最短路径

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
using namespace std;

typedef struct qnode{
	int i;
	int len;
	friend operator < (const qnode &n1, const qnode &n2)
	{
		return (n1.len > n2.len);
	}
}QNode;

void main()
{
	srand((unsigned)time(NULL));
	int n = 4;
	vector <int> dist;
	vector <int> parent;
	vector < vector <int> > c;
	c.resize(n);
	int i,j;
	for(i = 0; i < n; i++)
	{
		dist.push_back(0);
		parent.push_back(0);
		c[i].resize(n);
		c[i][i] = 0;
		for(j = 0; j < i; j++)
		{
			c[i][j] = rand() % 10;
			c[j][i] = c[i][j];
		}
	}

	priority_queue <QNode> Q;
	
	QNode E;
	E.i = 0;
	E.len = 0;

	while(1)
	{
		for(j = 0; j < n; j++)
		{
			if ((c[E.i][j] != 0)  && (E.len + c[E.i][j] < dist[j] || dist[j] ==0))
			{
				dist[j] = E.len + c[E.i][j];
				parent[j] = E.i;
				QNode x;
				x.i = j;
				x.len = dist[j];
				Q.push(x);
			}
		}

		if (Q.empty())
			break;
		else
		{
			E = Q.top();
			cout << E.i << setw(4) << E.len << endl;
			Q.pop();
		}
	}


	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n;j++)
			cout << setw(3) << c[i][j];
		cout << endl;
	}

	cout << "dist";
	for(i = 0; i< dist.size(); i++)
		cout << setw(3) << dist[i];
	cout << endl;
	cout << "the shortest length is:" << dist[n-1] << endl;

	
	cout << "parent";
	for(i= 0; i < parent.size(); i++)
		cout << setw(3) << parent[i];
	cout << endl;

	cout << "the path is ";
	cout << setw(3) << n-1;
	for(i = parent[n-1]; i!= 0; i = parent[i])
		cout << setw(3) << i;
	cout << setw(3) << 0;


	cout << endl;
	cout << endl;

		
}