dijkstra.cpp

实现Dijkstra算法：算法首先打印一个图

#include <iostream>
#include <stack>
#include <cfloat>
using namespace std;

class Graph
{
public:
	Graph(const char **g, int width, int height);
	~Graph();
	void findPath(int startNOdeId, int endNodeId, stack<int> &path);
	void printPath();
protected:
	// The id starts from 0.
	int getX(int id)
	{
		return id/_width;
	}
	int getY(int id)
	{
		return id%_width;
	}
	int getId(int x, int y)
	{
		return x*_width+y;
	}
	bool inBound(int newX, int newY)
	{
		return ( 0<=newX && newX<_height && 0<=newY && newY<_width );
	}

	char **_graph;
	int _width;
	int _height;
	int _vertex;
};
Graph::Graph(const char **g, int height, int width)
{	
	_height = height;
	_width = width;
	_vertex = _width * _height;

	_graph = new char*[_height];
	for(int i = 0; i < _height; i++)
	{
		_graph[i] = new char[_width];
	}

	for(int row = 0; row < _height; row++)
	{
		for(int col = 0; col < _width; col++)
		{
			_graph[row][col] = g[row][col];
		}
	}
	
	for(int row = 0; row < _height; row++)
	{
		for(int col = 0; col < _width; col++)
			cout << _graph[row][col];
		cout << endl;
	}
}
Graph::~Graph()
{
	for(int i = 0; i < _height; i++)
	{
		delete []_graph[i];
	}
	delete []_graph;
}

void Graph::findPath(int startNodeId, int endNodeId, stack<int> &path)
{
	if( 'X' == _graph[getX(startNodeId)][getY(startNodeId)] 
	    || 'X' == _graph[getX(startNodeId)][getY(startNodeId)] )
	{ return; }

	bool *reach = new bool[_vertex]; // Flag whether the shortest path is found.
	int *precedence = new int[_vertex]; // Record the precedence of a vertex.
	double *dis = new double[_vertex]; // Record the current distance of a node from startNodeId.

	// Initialization
	for(int i = 0; i < _vertex; i++){	reach[i] = false; }
	for(int i = 0; i < _vertex; i++){	precedence[i] = -1;	}
	for(int i = 0; i < _vertex; i++){	dis[i] = DBL_MAX; }
	dis[startNodeId] = 0;

  for(int i = 0; i < _vertex; i++)
	{
		int smallestId;
		int min = INT_MAX;
		for(int j = 0; j < _vertex; j++)
		{// Find the one with smallest dis and non-reached.
			if( !reach[j] && min>dis[j] && 'X'!=_graph[getX(j)][getY(j)] )
			{
				smallestId = j;
				min = dis[j];
			}
		}
		// Relax : precedence, dis, reach.
		if( INT_MAX == min )
			break;
		reach[smallestId] = true;
		// For it's eight neighbours that're unreached.
		int x = getX(smallestId), y = getY(smallestId);
		int xShift[3] = {-1, 0, 1}, yShift[3] = {-1, 0, 1};
		for(int m = 0; m < 3; m++)
		{
			for(int n = 0; n < 3; n++)
			{
				if( !xShift[m] && !yShift[n] ) continue; // The current point (j).
				int newX= x + xShift[m], newY = y + yShift[n];
				int currentId = getId(newX, newY);
				if(	inBound(newX, newY) && 'X'!=_graph[newX][newY] && !reach[currentId] )
				{
					int tmp = 100 + (xShift[m] && yShift[n]) * 41;
					if( dis[smallestId] + tmp < dis[currentId] )
					{
						precedence[currentId] = smallestId;
						dis[currentId] = dis[smallestId] + tmp;
					}

				}
			}
		}
		if( reach[endNodeId] ){ break; }
	}

	if( -1 != precedence[endNodeId] )
	{
		int i = endNodeId;
		while( -1 != i )
		{
			path.push(i);
			i = precedence[i];
		}
	}
	
	delete []reach;
	delete []precedence;
	delete []dis;
}

void Graph::printPath()
{
	
}

int main()
{
	const char *g[6] =
	{
		" XX     ",
		"  X XXXX",
		" XX     ",
		" XX XX  ",
		"    XX  ",
		"XXXXXXX "
	};
	int h = 6, w = 8;
	
	Graph graph(g, h, w);

	stack<int> path;

	int start, end;
	cout << "enter start node id:	" << endl;
	cin >> start;
	cout << "enter end node id:	" << endl;
	cin >> end;
	graph.findPath(start, end, path);

	if( path.empty() )
	{
		cout << "between them no path!" << endl;
	}
	else
	{
		cout << "between them the path is:	" << endl;
		while( !path.empty() )
		{
			int tmp = path.top();
			path.pop();
			cout << "(" << tmp/w << ", " << tmp%w << ")";
			if( !path.empty() )
			cout << "--->";
		}
		cout << endl;
	}

	return 0;
}