多段图的最短路径

       多段图是一个有向的无环图。求解从起始点v0到终止点的最短路径的长度，首先看一下这个问题是否具有最优子结构的性质。对于每一点来说，从v0到它的最短路径有两种可能，分别是从v0直接到该点或者是从最短的前驱节点开始到该节点。从这里可以看出有递归的性质，所以使用回溯的方法也是可以解决的。即从终点开始，依次向前找到最短的路径。由于递归本身所用的时间较长，并且在回溯的过程中存在重复的工作，所以使用动态规划更好。

       解决的多段图如下所示：

        解决的描述为：

         1. 初始化待解决的图，初始化从v0 到各个节点的距离向量distance 。distance[0] = 0, 其余初始化为MAX。初始化图的弧arc [][]的权值，如果两个图的定点没有相连，初始化为MAX。设置path[] 用于记录在寻找最短路径时节点i选择的前驱节点path[i]。

         2. 从节点1开始，获取该节点的所有的前驱节点。记当前节点为currentnode,当前节点的某个前驱节点为pre[i], (i >= 0 并且 i < pre.size)。设置标记当前节点选择的前驱节点min_i， v0 到当前节点的最短路径的长度 min_length，初始化为distance[currentnode]。对于pre中的每一个节点比较pre[i]+arc[currnode][i] 与min_length ,如果前面的值更小，更新min_i 与min_length。当所有的子节点全部遍历过后，将path[currentnode] = min_i，distance[currentnode] = min_length。

         3. 寻找到终结点后, 记终结点为lastnode, 则最短路径的长度为distance[lastnode]。从path[lastnode] 开始 lastnode = path[lastnode] 直到v0 为止，输出最短路径上的节点。

算法实现：

         arc 与distance 可以使用矩阵、数组表示，不过为了再次练习使用C++的模板等一些东西，所以实现上不够简洁。代码如下所示：

#include <iostream>

using namespace std;

//用于distance与arc的节点
struct arc_node {
	int startnode;		//起始节点的编号
	int endnode;		//终止节点的编号
	int weight;			//弧的权值

	struct arc_node *next;

	arc_node() :startnode(-1), endnode(-1), weight(INT_MAX),next(nullptr) {}
	struct arc_node& operator =(const struct arc_node &other) {
		this->startnode = other.startnode;
		this->endnode = other.endnode;
		this->weight = other.weight;
		return *this;
	}

	arc_node(int startnode, int endnode, int w) :startnode(startnode), endnode(endnode), weight(w),next(nullptr) {}
};

ostream & operator << (ostream &out, arc_node obj) {
	out << "start :" << obj.startnode << ", end：" << obj.endnode << ", weight：" << obj.weight << endl;
	return out;
}
//用于存储每个节点选择的最短路径的前一个编号
struct path_select {
	int currnode;			//当前节点编号
	int before_select;		//选择的最短路径的前驱节点

	struct path_select *next;

	path_select(int currnode, int before_select) :currnode(currnode), before_select(before_select),next(nullptr) {}
	path_select() :currnode(-1), before_select(-1),next(nullptr) {}

	struct path_select& operator =(const struct path_select &other) {
		this->currnode = other.currnode;
		this->before_select = other.before_select;
		return *this;
	}

};

struct my_pair {
	int first;
	int second;

	struct my_pair *next;

	my_pair() :first(-1), second(-1), next(nullptr) {}
	my_pair(int first, int second) :first(first), second(second), next(nullptr) {}

	struct my_pair& operator =(const struct my_pair &other) {
		this->first = other.first;
		this->second = other.second;
		return *this;
	}
};

template <class T>
class MyQ {
public:
	T * queueStart;
	int size;

	MyQ();
	~MyQ();

	void push(T e);		//从后边加入
	T pop();			//弹出队首
	T* get(int i);		//得到下标为i的元素的指针
	bool empty();		//队列是否为空
};
//构造函数
template<class T>
MyQ<T>::MyQ(){
	queueStart = new T();
	size = 0;
}
//销毁函数
template<class T>
MyQ<T>::~MyQ(){

}
//加入一个新的元素
template<class T>
void MyQ<T>::push(T e){
	T *p = queueStart;
	while (p->next != nullptr)
		p = p->next;
	T *newnode = new T();
	*newnode = e;
	p->next = newnode;
	++size;
}
//弹出队首元素
template<class T>
T MyQ<T>::pop(){
	T *p = queueStart;
	T e;
	e = *p->next;
	p->next = p->next->next;
	--size;
	return e;
}

template<class T>
T * MyQ<T>::get(int i){
	if (i < 0 || i >= size)
		return nullptr;
	int index = -1;
	T *p = queueStart;
	while (p != nullptr) {
		++index;
		p = p->next;
		if (index == i)
			return p;
	}

	return nullptr;
}

template<class T>
bool MyQ<T>::empty(){
	return (size == 0 ? true : false);
}

//寻找多段图的最短路径
class Solution {
public:
	MyQ<struct arc_node> dis;		//用于在寻找最短路径中更新路径
	MyQ<struct arc_node> arcs;		//用于存储初始的多段图的弧
	MyQ<struct path_select> path;		//用于记录最短路径的选择

	Solution();

	MyQ<struct my_pair> getPreNodes(int nodecode);	//获取当前节点的前驱节点队列
	int getThisArc(int start, int end);	//获取该弧的权重
	void traverseDis();		//遍历distance
	void outputShortestPath();		//输出最短路径上的节点的编号

	void findShortestPath();
};

Solution::Solution(){
	arcs.push(struct arc_node(0, 1, 4));
	arcs.push(struct arc_node(0, 2, 2));
	arcs.push(struct arc_node(0, 3, 3));
	arcs.push(struct arc_node(1, 4, 9));
	arcs.push(struct arc_node(1, 5, 8));
	arcs.push(struct arc_node(2, 4, 6));
	arcs.push(struct arc_node(2, 5, 7));
	arcs.push(struct arc_node(2, 6, 8));
	arcs.push(struct arc_node(3, 5, 4));
	arcs.push(struct arc_node(3, 6, 7));
	arcs.push(struct arc_node(4, 7, 5));
	arcs.push(struct arc_node(4, 8, 6));
	arcs.push(struct arc_node(5, 7, 8));
	arcs.push(struct arc_node(5, 8, 6));
	arcs.push(struct arc_node(6, 7, 6));
	arcs.push(struct arc_node(6, 8, 5));
	arcs.push(struct arc_node(7, 9, 7));
	arcs.push(struct arc_node(8, 9, 3));

	//初始化distance
	dis.push(struct arc_node(0, 0, 0));
	for (int i = 1; i < 10; ++i)
		dis.push(struct arc_node(0, i, INT_MAX));

}

//寻找当前节点的所有的前驱节点编号
MyQ<struct my_pair> Solution::getPreNodes(int nodecode){
	MyQ<struct my_pair> result;
	for (int i = 0; i < arcs.size; ++i) {
		cout << i << endl;
		if (arcs.get(i) != nullptr && arcs.get(i)->endnode == nodecode) {
			result.push(struct my_pair(arcs.get(i)->startnode, nodecode));
		}
	}
	return result;
}
//返回该弧的权重
int Solution::getThisArc(int start, int end){
	for (int i = 0; i < arcs.size; ++i)
		if (arcs.get(i)->startnode == start && arcs.get(i)->endnode == end)
			return arcs.get(i)->weight;
	return INT_MAX;
}

//寻找最短的路径
void Solution::findShortestPath(){
	//从节点1开始，依次向后寻找最短路径
	MyQ<struct my_pair> prenodes;	//记录前驱节点编号的队列
	int preid;		//前驱节点的编号
	int minweight = INT_MAX, selectid = 0;

	for (int i = 1; i < 10; ++i) {
		cout << "当前计算到的节点编号：" << i << endl;
		prenodes = getPreNodes(i);
		cout << "前驱节点的个数：" << prenodes.size << endl;
		minweight = INT_MAX;
		selectid = 0;
		while(!prenodes.empty()) {
			preid = prenodes.pop().first;
			cout << "当前比较选择前驱 " << preid << " weight " << dis.get(preid)->weight + getThisArc(preid, i)
				<< " 和当前的Min = " << minweight << endl;
			if ((dis.get(preid)->weight + getThisArc(preid, i)) < minweight) {
				minweight = dis.get(preid)->weight + getThisArc(preid, i);
				selectid = preid;

			}		
		}
		traverseDis();
		//记录选择的最短的路径
		path.push(struct path_select(i, selectid));	//加入到path 记录中
		dis.get(i)->weight = minweight;		//更新distance
		cout << "当前节点 " << i << "  选择了前驱节点：" << selectid << " dis[i] = " << dis.get(i)->weight << endl;
		cout << endl;
	}
	cout << "最短的路径的长度是：" << dis.get(9)->weight << endl;
	traverseDis();
}

void Solution::traverseDis(){
	cout << "遍历 distance" << endl;
	for (int i = 0; i < dis.size; ++i) {
		cout << dis.get(i)->weight << "  ";
	}
	cout << endl;
}
//输出最短路径上的节点的编号
void Solution::outputShortestPath(){
	cout << "反向输出最短路径：" << endl;
	int nodeid = path.get(path.size - 1)->currnode;

	do {
		cout << nodeid << "<--";
		for(int i=0;i<path.size;++i)
			if (path.get(i)->currnode == nodeid) {
				nodeid = path.get(i)->before_select;
				break;
			}
	} while (nodeid != 0);
	cout << "0" << endl;
}

int main()
{
	Solution solution;
	solution.findShortestPath();	
	solution.outputShortestPath();
    return 0;
} 

运行的部分截图：