编辑代码

#include<iostream>
using namespace std;
#define INT_MAX 2147483647
class queueINT {
private:
	int front;
	int rear;
	int* head;
	int length;
public:
	queueINT(int len);
	~queueINT();
	void push(int e);
	int pop();
	bool isEmpty();
	int howLong();
};

queueINT::queueINT(int len)
{
	if (len <= 1) {
		cout << "in queueINT(int len), len is too small" << endl;
		len = 100;
	}
	head = new int[len];
	length = len;
	front = 0, rear = 0;
}

queueINT::~queueINT()
{
	if (head != nullptr) {
		delete[] head;
	}
}

void queueINT::push(int e)
{
	if ((rear + 1) % length == front)
	{
		//队满
		int* newhead = new int[length * 2];
		for (int i = 0; i < length - 1; i++)
		{
			newhead[i] = head[(front + i) % length];
		}
		delete[]head;
		head = newhead;
		front = 0, rear = length - 1;
		length *= 2;
	}
	head[(rear++) % length] = e;
}

int queueINT::pop()
{
	if (front == rear) {
		return INT_MAX;
	}
	return head[(front++) % length];
}

bool queueINT::isEmpty()
{
	return front == rear;
}

int queueINT::howLong()
{
	return (rear - front + length) % length;
}



class stackINT {
private:
	int* base;
	int* top;
	int length;
public:
	stackINT(int len);
	~stackINT();
	void push(int e);
	int pop();
	bool isEmpty();
};

stackINT::stackINT(int len)
{
	length = len;
	base = new int[len];
	top = base;
}

stackINT::~stackINT()
{
	top = nullptr;
	if (base != nullptr) delete[]base;
}

void stackINT::push(int e)
{
	if (top - base == length) {
		int* newbase = new int[length * 2];
		for (int i = 0; i < length; i++) {
			newbase[i] = base[i];
		}
		delete []base;
		base = newbase;
		top = length + base;
		length *= 2;
	}
	*(top++) = e;
}

int stackINT::pop()
{
	if (isEmpty()) {
		return INT_MAX;
	}
	top--;
	return *top;
}

bool stackINT::isEmpty()
{
	return top == base;
}


class Dijkstra
{
public:
	Dijkstra();
	~Dijkstra();
	Dijkstra(int**& matrix, int sumOfNodes);
	void showNodes();
	//用Dijkstra算法求出编号为start的节点到其他节点的最短路径
	void shortestWay(int start);
	//输出最短路径
	void showShortest(int start);
private:
	typedef struct Way {
		//存储所有与某个节点有关联的路径信息,nextNum为与其相连的另一节点,val为路径的权重,sumOfWays为该节点度数
		int* nextNum;
		int* val;
		int sumOfWays;
		Way()
		{
			nextNum = nullptr, val = nullptr;
			sumOfWays = 0;
		}
		Way(int n)
		{
			nextNum = new int[n];
			val = new int[n];
			sumOfWays = n;
			for (int i = 0; i < n; i++) {
				nextNum[i] = 0, val[i] = 0;
			}
		}
		~Way()
		{
			if (nextNum != nullptr) delete[] nextNum;
			if (val != nullptr) delete[]val;
		}
		void assign(int n, int next, int value)
		{
			//插入新值,参数依次为下标,相邻节点编号,权重
			if (n < 0 || n >= sumOfWays) {
				cout << "in Dijkstra, struct Way, void assign, n is out of arrange;" << endl;
				exit(0);
			}
			nextNum[n] = next, val[n] = value;
		}
	}Way;
	typedef struct Node {
		//保存某一结点编号以及和其相关联的路径
		int num;
		Way ways;
		Node(int _num,int lenOfWays):ways(lenOfWays) {
			num = _num;
		}
	}Node;
	typedef struct Signs {
		//存储用标号法求解过程中获得的中间及最终结果
		//priorNum为到当前节点的上一个节点的编号,sumCost表示到当前节点的花销之和
		//startNum是初始节点编号
		int* priorNum;
		int* sumCost;
		int startNum;
		Signs()
		{
			startNum = 0;
			priorNum = nullptr, sumCost = nullptr;
		}
		Signs(int start, int n)
		{
			startNum = start;
			priorNum = new int[n+1];
			sumCost = new int[n+1];
			for (int i = 0; i <= n; i++) {
				priorNum[i] = start;
				sumCost[i] = INT_MAX;
			}
			sumCost[start] = 0;
		}
		~Signs()
		{
			if (priorNum != nullptr) delete[] priorNum;
			if (sumCost != nullptr) delete[]sumCost;
		}
	}Signs;
	Node** nodes;
	Signs** signs;
	int jie;
};

Dijkstra::Dijkstra()
{
	nodes = nullptr;
	signs = nullptr;
	jie = 0;
}

Dijkstra::~Dijkstra()
{
	if (nodes != nullptr) {
		for (int i = 0; i < jie; i++) {
			delete nodes[i];
		}
		delete nodes;
	}
	if (signs != nullptr) {
		for (int i = 0; i < jie; i++) {
			delete signs[i];
		}
		delete signs;
	}
}

Dijkstra::Dijkstra(int**& matrix, int sumOfNodes)
{
	jie = sumOfNodes;
	nodes = new Node*[sumOfNodes];
	signs = new Signs*[sumOfNodes];
	//表示matrix中各行非零元个数
	int* temp = new int[sumOfNodes];
	for (int i = 0; i < sumOfNodes; i++)
	{
		temp[i] = 0;
		for (int j = 0; j < sumOfNodes; j++) {
			if (matrix[i][j]) temp[i]++;
		}
	}
	for (int i = 0; i < sumOfNodes; i++) {
		nodes[i] = new Node(i + 1, temp[i]);
		for (int j = 0, k = 0; j < sumOfNodes; j++) {
			if (matrix[i][j]) nodes[i]->ways.assign(k++, j + 1, matrix[i][j]);
		}
		signs[i] = new Signs(i + 1, sumOfNodes);
	}
}

void Dijkstra::showNodes()
{
	for (int i = 0; i < jie; i++)
	{
		cout << nodes[i]->num << ' ';
		for (int j = 0; j < nodes[i]->ways.sumOfWays; j++) {
			cout << '<' << nodes[i]->ways.nextNum[j] << ", " << nodes[i]->ways.val[j] << '>' << ' ';
		}
		cout << endl;
	}
}

void Dijkstra::shortestWay(int start)
{
	queueINT q(jie);
	//表示某一结点是否被计算
	int* isRepeat = new int[jie + 1];
	for (int i = 0; i <= jie; i++)isRepeat[i] = 0;
	int curNum = 0, nextNum = 0;
	q.push(start);
	isRepeat[start] = 1;
	while (!q.isEmpty())
	{
		curNum = q.pop();
		for (int i = 0; i < nodes[curNum-1]->ways.sumOfWays; i++) {
			nextNum = nodes[curNum - 1]->ways.nextNum[i];
			//for (int i = 0; i <= jie; i++) cout << isRepeat[i] << ' ';
			if (isRepeat[nextNum] == 0) {
				q.push(nextNum);
				isRepeat[nextNum] = 1;
			}
			if (nodes[curNum - 1]->ways.val[i] + signs[start - 1]->sumCost[curNum] < signs[start - 1]->sumCost[nextNum])
			{
				int a = nodes[curNum - 1]->ways.val[i];
				int b = signs[start - 1]->sumCost[curNum];
				int d = signs[start - 1]->sumCost[nextNum];
				int c = signs[start - 1]->priorNum[nextNum];
				signs[start - 1]->priorNum[nextNum] = curNum;
				signs[start - 1]->sumCost[nextNum] = nodes[curNum - 1]->ways.val[i] + signs[start - 1]->sumCost[curNum];
			}
		}
	}
}

void Dijkstra::showShortest(int start)
{
	if (start < 1 || start > jie) {
		cout << "In Dijkstra, void showShortest, start is out of range" << endl;
		return;
	}
	for (int i = 0; i < jie; i++) {
		if (signs[start]->sumCost[i] == INT_MAX) {
			shortestWay(start);
			i = jie;
		}
	}
	for (int i = 1, curPoint = 0; i <= jie; i++) {
		if (i != start) {
			//存储经过的路径
			int k = 0, * temp = new int[jie];
			curPoint = i;
			do {
				temp[k++] = curPoint;
				curPoint = signs[start-1]->priorNum[curPoint];
			} while (curPoint != start);
			cout << start;
			while (--k >= 0) {
				cout << temp[k];
			}
			cout << "  ";
			cout << signs[start - 1]->sumCost[i];
			cout << endl;
		}
	}
}

int main()
{
	int** p;
	int n = 6;
	p = new int* [n];
	for (int i = 0; i < n; i++)p[i] = new int[n];
	for (int i = 0, temp = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			//输入
			//(7)0 3 7 5 0 0 0 3 0 2 0 6 0 0 7 2 0 3 3 0 0 5 0 3 0 0 2 8 0 6 3 0 0 0 2 0 0 0 2 0 0 2 0 0 0 8 2 2 0
			//(6)0 4 8 0 0 0 4 0 2 3 6 0 8 2 0 2 0 8 0 3 2 0 3 1 0 6 0 3 0 6 0 0 8 1 6 0
            //(6)0 12 19 28 40 59 12 0 13 20 29 41 19 13 0 14 21 30 28 20 14 0 15 22 40 29 21 15 0 16 59 41 30 22 16 0
			cin >> temp;
			p[i][j] = temp;
		}
	}
	Dijkstra dj(p, n);
	dj.showNodes();
	dj.showShortest(1);
	for (int i = 0; i < n; i++)delete p[i];
	delete p;
	return 0;
}