Yen算法求前K短路

Yen算法求前K短路，无向图中求Yen算法求前K短无环路。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef char VT;//点
typedef int LT;//边

const VT MAX_VER = 50;
const LT MAX_LEN = 99999999;

struct Edge
{
    VT to;
    LT len;
    Edge* next;

    Edge（VT t = 0 LT l = 0 Edge* n = NULL）
    {
        to = t;
        len = l;
        next = n;
    }
};

struct Path
{
    vector node;
    vector block;
    LT len;

    //偏差结点. 前驱节点在第K短树的路径上
    VT dev;

    Path（VT v = 0） : node（） block（）
    {
        node.push_back（v）;
        len = 0;
    }

    bool operator > （const Path& p） const
    {
        return len > p.len || len == p.len
               && lexicographical_compare（
                   p.node.rbegin（） p.node.rend（）
                   node.rbegin（） node.rend（） ）;
    }
};

ostream& operator << （ostream& os const Path& p）
{
    os << p.node[ p.node.size（） - 1 ] + 1;
    for （int i = p.node.size（） - 2; i >= 0; i--）
    {
        os << “->“ << p.node[i] + 1;
    }
    return os;
}

class Graph
{
public:
    Graph（）
    {
        memset（m_adj 0 sizeof（m_adj））;
    }
    ~Graph（）
    {
        init（）;
    }

    //对边的判重
    void addEdge（VT from VT to LT len）
    {
        if （ NULL == m_edge[from][to] ）
        {
            m_adj[from] = new Edge（to len m_adj[from]）;
            m_edge[from][to] = m_adj[from];
        }
    }

    void dijkstra（）
    {
        int minV;
        for （int iter = 0; iter < m_verCnt; iter++）
        {
            minV = -1;
            for （int i = 0; i < m_verCnt; i++）
            {
                if （!m_visit[i]
                        && （minV==-1 || m_sh[i] < m_sh[minV] ）
                   ）
                {
                    minV = i;
                }
            }
            if （minV==-1）  break;
            m_visit[minV] = true;
            for （Edge* adj = m_adj[minV]; adj; adj = adj->next）
            {
                VT to = adj->to;
                //满足条件 “!m_visit[to]“
                if （!m_visit[to] && !m_block[minV][to]）
                    relax（minV to adj->len）;
            }
        }
    }

    void init（VT verCnt = MAX_VER）
    {
        memset（ m_edge 0 sizeof（m_edge） ）;
        m_verCnt = verCnt;
        Edge* p *temp;
        for （VT i = 0; i < m_verCnt; i++）
        {
            p = m_adj[i];
            while （p）
            {
                temp = p;
                p = p->next;
                delete temp;
            }
            m_adj[i] = NULL;
        }
    }

    //Yen算法求出K短路径，如果有两相同长度的路径，取源节点标号小的为第k短
    vector yenLoopless（VT source VT sink int k）
    {
        vector result;
        priority_queue< Path vector greater > candidate;
        memset（m_block 0 sizeof（m_block））;
        initSingleSrc（source）;
        dijkstra（）;
        if （ sh

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     163328  2009-09-12 16:08  前k短路.ppt

     文件       7740  2009-09-11 08:34  main.cpp

----------- ---------  ---------- -----  ----

               171068                    2