c7_dijkstra.cpp

这个是严蔚敏版的数据结构上机教程中的部分源代码

/*
ID:  wangyucao
PROB:heap+dijkstra
LAUG:C++
*/
#include <iostream>
#include <fstream>
#include <memory>
#include <queue>
#include <vector>
#define Max 100
const int Maxint=0x7fffffff;
using namespace std;

struct Node{
	int Adjvex;
	int val;
};
int dis[Max],n,start;
int map[Max][Max];
struct cmp{
	bool operator()(Node a,Node b)
	{
		return a.val>b.val;
	}
};
vector<int> edge[Max];
priority_queue<Node,vector<Node>,cmp> mq;
//queue<int> way;
bool used[Max];

void init()
{
	int i,m,a,b,l;
	cout<<"输入定点数，边数和起点："<<endl;
	cin>>n>>m>>start;
	start--;
	for(i=0;i<m;i++)
	{
		cin>>a>>b>>l;
		a--;b--;
		map[a][b]=l;
		//map[b][a]=l;
		edge[a].push_back(b);
		//edge[b].push_back(a);
	}
	for(i=0;i<n;i++) dis[i]=Maxint;
}

void dijkstra(int start)
{
	int i,j,k;
	Node temp,temp1;
	temp.Adjvex=start;
	temp.val=0;
	dis[temp.Adjvex]=0;
	mq.push(temp);
	while(!mq.empty())
	{
		temp=mq.top();
		mq.pop();
		used[temp.Adjvex]=true;
		//dis[temp.Adjvex]=temp.val;
	//	way.push(temp.Adjvex);
		for(j=0;j<edge[temp.Adjvex].size();j++)
		{
			i=edge[temp.Adjvex][j];
			if(dis[temp.Adjvex]+map[temp.Adjvex][i]<dis[i] && !used[i])
			{
				dis[i]=dis[temp.Adjvex]+map[temp.Adjvex][i];
				temp1.Adjvex=i;
				temp1.val=dis[i];
				mq.push(temp1);
			}
		}
	}
}
void output()
{
	for(int i=0;i<n;i++)
		if(i!=start) cout<<start+1<<"到定点"<<i+1<<"的最短距离为："<<dis[i]<<endl;
}
void test_out()
{
	while(!mq.empty())
	{
		cout<<mq.top().val<<' ';
		mq.pop();
	}

}
int main()
{
	memset(used,false,sizeof(used));
	init();
	dijkstra(start);
	output();
	system("PAUSE");
	return 0;
}