k_shortest_path.h

中文分词, N-最短路径算法 ICTCLAS研究学习组 http://groups.google.com/group/ictclas?msg=subscribe

//k_shortest_path.h
#pragma once

#include ".\adj_list.h"
//#include <list>

typedef std::vector<NODE_ID_TYPE> path_id_list_t;
typedef std::pair< COST_TYPE, path_id_list_t > path_t;
typedef std::vector<path_t> k_paths_t;

class KShortestPath{
protected:
	struct pre_node_entry{
		COST_TYPE c_weight;
		NODE_ID_TYPE c_PreNode;
		size_t c_PreIndex;
		pre_node_entry(NODE_ID_TYPE node, size_t index, const COST_TYPE& weight)
			:	c_PreNode(node), c_PreIndex(index), c_weight(weight){}

			bool operator< (const pre_node_entry& entry2)
			{
				return c_weight<entry2.c_weight;
			}
	};
	typedef std::vector< pre_node_entry > node_item_t;
	typedef std::vector< node_item_t > node_item_list_t;
	
public:
	//	Constructor
	KShortestPath(adj_list& g) : c_g(g) { c_node_items.resize(g.get_vert_count()); }
	//	Find K shortest path
	void Find(const size_t k, k_paths_t& resPaths);

protected:
	void GetPaths(k_paths_t& result);

protected:
	adj_list& c_g;
	node_item_list_t c_node_items; //the item list for the  c_g

};