dijkstra.cpp

时间复杂度为O(ElogV)的Dijkrastra算法的实现

//////////////////////////////////////////////////////////////////////////
// 用Dijkrastra算法计算城市道路网的最短路径，时间复杂度为O(ElogV)
// 刘金义－－辽宁石油化工大学工程软件研究所
// [e-mail]
//////////////////////////////////////////////////////////////////////////
#include <vector>
#include <stdio.h>
#include <time.h>
#include <conio.h>
using namespace std;
typedef unsigned int uint; 

#include "Heap.h"

void PrintPath(Heap& Q, int& n, int row, int col)
{
	if(row==0 && col==0)
		printf("(0,0)");
	else
	{
		PrintPath(Q, n, Q.Path[row*n+col].prerow, Q.Path[row*n+col].precol);
		printf("-(%d,%d)", row, col);
	}
}

void Dijkstra(vector<vector<uint> > &w1, vector<vector<uint> > &w2, int& m, int& n)
{
	Heap Q(m, n);
	int i, j, num=1;

//initializing
	for(i=0; i<m; i++)
	{
		for(j=0; j<n; j++)
		{
			Vertex v;
			v.row = i;
			v.col = j;
			if(i==0 && j==0)
				v.d = 0;
			else
				v.d = 0xFFFFFFFF;
			Q.Add(num++, v);
		}
	}

	uint dmin = 0;
	while(Q.HeapSize()>0)
	{
		Vertex u = Q.ExtractMin();
		if(u.row==m-1 && u.col==n-1)
		{
			dmin = u.d;
			break;
		}
		Q.M[u.row * n + u.col] = -1;
		if(u.row != m-1)
			Q.DecreaseKey(u, u.row+1, u.col, w2[u.row][u.col]);
		if(u.row != 0)
			Q.DecreaseKey(u, u.row-1, u.col, w2[u.row-1][u.col]);
		if(u.col != n-1)
			Q.DecreaseKey(u, u.row, u.col+1, w1[u.row][u.col]);
		if(u.col != 0)
			Q.DecreaseKey(u, u.row, u.col-1, w1[u.row][u.col-1]);
	}
	
	printf("最优路径为：");
	PrintPath(Q, n, m-1, n-1);
	printf("\n最优值为：%d\n", dmin);
}

main()
{
	int m, n;
	vector<vector<uint> > w1, w2;
	char filename[128];
	FILE *file;
	int i, j;

	printf("需要随机产生一个权值文件吗？(Y/N)");
	char answer;
	scanf("%c", &answer);
	if(answer=='y' || answer=='Y')
	{
		printf("要生成的权值文件名:");
		scanf("%s", filename);
		file = fopen(filename, "w");
		printf("城市横向路的个数(2-1000):");
		scanf("%d", &m);
		printf("城市纵向街的个数(2-1000):");
		scanf("%d", &n);

		fprintf(file, "%d\n%d\n", m, n);
		srand((unsigned)time(NULL));
		for(i=0; i<m; i++)
		{
			fprintf(file, " ");
			for(j=0; j<n-1; j++)
				fprintf(file, "%d ", int(1.0*rand()/RAND_MAX*100));
			fprintf(file, "\n");
			if(i==m-1)
				continue;
			for(j=0; j<n; j++)
				fprintf(file, "%d ", int(1.0*rand()/RAND_MAX*100));
			fprintf(file, "\n");
		}
		fclose(file);
	}

	printf("\n将计算的权值文件名:");
	scanf("%s", filename);
	if((file=fopen(filename, "r"))==NULL)
	{
		printf("Error: the graph file does not exist.\n");
		return 1;
	}
time_t t_start = time(NULL);
	fscanf(file, "%d %d", &m, &n);
	printf("路数×街数:%d×%d\n", m, n);
	for(i=0; i<m; i++)
	{
		vector<uint> v;
		for(j=0; j<n-1; j++)
		{
			uint x;
			fscanf(file, "%d", &x);
			v.push_back(x);
		}
		w1.push_back(v);
		
		if(i==m-1)
			continue;
		v.clear();
		for(j=0; j<n; j++)
		{
			uint x;
			fscanf(file, "%d", &x);
			v.push_back(x);
		}
		w2.push_back(v);
	}
	fclose(file);
/*
	for(i=0; i<m; i++)
	{
		printf(" ");
		for(j=0; j<n-1; j++)
			printf("%d ", w1[i][j]);
		printf("\n");
		if(i==m-1)
			continue;
		for(j=0; j<n; j++)
			printf("%d ", w2[i][j]);
		printf("\n");
	}
*/
	Dijkstra(w1, w2, m, n);
printf("时间消耗：%g\n", difftime(time(NULL), t_start));
_getch();
	return 1;
}