68wih4.rar

68wih4.rar

#include  
#include 
#include 
#include 
#include 
 
using namespace std;
 
#define MAX_NODE 26 // 最大结点数
#define COST_NO_link    INT_MAX // 定义结点之间没有连接的花销为INT_MAX吗
 
int Graph[MAX_NODE][MAX_NODE];
int Cost[MAX_NODE][MAX_NODE];
int V_dingdianshu E_bianshu Start_Point; // 顶点数和边数，以及开始的起点（以0开始）
 
int Odd_Grouping[MAX_NODE]; // 为0表示不为奇，为1表示为奇，从2开始表示配对分组情况，如同为2的两个为一组，同为3的两个为一组，……
int Bak_Odd_Grouping[MAX_NODE]; // 最好情况下分组策略的备份，因为可能还有其他情况更好，如果有，就更新此备份。
int SHORTEST_PATH_WEIGHT（COST_NO_link）; // 如果存在奇度数点，这里是记录的添加最短路径的最小值，是所有点两两分组的最短路径之和的最小值。此值对应Bak_Odd_Grouping所描述的分组情况。
 
int Dist[MAX_NODE]; // Dijstra算法中，求从v0到v1最短路径结果，里面包含v0到最短路径上各点的最短权值
int ShortCache[MAX_NODE][MAX_NODE]; // Dijstra算法中，求点v0到v1的最短路径记录值，当第一次求时，把结果存到本数组中，下次如果还在相同调用，则直接返回本数组中相应值。
 // 数据输入，会用到Graph和Cost
void Input（）
{
    int i j;
    int m n;
    char cs cm cn;
    int w;
    cout<< “输入图的顶点数：“;
    cin>> V_dingdianshu;
    cout<<“输入图边的数目：“;
    cin>>E_bianshu;
    cout<<“输入起点：“;
    cin>>cs;
    Start_Point = cs - ‘a‘;
    for（i = 0; i < V_dingdianshu; i++）
    {
        for（j = 0; j < V_dingdianshu; j++）
        {
            Graph[i][j] = 0;
            ShortCache[i][j] = 0;
            Cost[i][j] = COST_NO_link;
        }
        Cost[i][i] = 0; // 置自己到自己为0
    }
  cout << “输入“ << E_bianshu << “条边对应的顶点和权值（顶点从a开始编号）：“ << endl;
    for（i = 0; i < E_bianshu; i++）
    {
        cin >> cm >> cn >> w;
        m = cm - ‘a‘;
        n = cn - ‘a‘;
        Graph[m][n] += 1;
        Graph[n][m] += 1;
        Cost[m][n] = w;
        Cost[n][m] = w;
    }
}
int Dijstra（int v0 int v1 bool useCache）
{
    if（useCache && ShortCache[v0][v1] != 0） // 之前计算过了，直接返回值
    {
        return ShortCache[v0][v1];
    }
    int i s w min minIndex;
    bool Final[MAX_NODE];
    for （s = 0; s < V_dingdianshu; s++）// 初始化最短路径长度数据，所有数据都不是最终数据
    {
        Final[s] = false;
        Dist[s] = COST_NO_link; // 初始最大距离
    }
    Final[v0] = true;// 首先选v0到v0的距离一定最短，最终数据 
    Dist[v0] = 0;
    s = v0; // 0 预先选中v0点
   for （i = 0; i < V_dingdianshu; i++）
    {
      for（w = 0; w < V_dingdianshu; w++）// 1 更新该点到其他未选中点的最短路径
        {
            if（!Final[w] // w点未选中
                && Cost[s][w] < COST_NO_link // 更新点应该与选中点s相连
                && Dist[w] > Dist[s] + Cost[s][w]） // 通过点s会有更短的路径
            {
                if（Dist[s] + Cost[s][w] <= 0）
                {
                    cout << “求最短路径数据溢出。“ << endl;
                    exit（-1）;
                }
                Dist[w] = Dist[s] + Cost[s][w];
            }
        }
	 if（s == v1）// 1.5 如果在中间过程找到了目标点v1，则不再继续计算了
        {
            ShortCache[v0][v1] = Dist[s];
            ShortCache[v1][v0] = Dist[s];
            return Dist[s];
        }
        min = COST_NO_link;// 2 选中相应点
        for（w = 0; w < V_dingdianshu; w++）
        {
            if（!Final[w] // 未选中
                && Dist[w] < min） // 值更小
           

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

     文件     342813  2014-07-03 15:06  中国邮路\Debug\main.obj

     文件      82944  2014-08-03 16:30  中国邮路\Debug\vc60.idb

     文件     143360  2014-07-03 15:06  中国邮路\Debug\vc60.pdb

     文件     577605  2014-07-03 15:06  中国邮路\Debug\中国邮路.exe

     文件     813704  2014-07-03 15:06  中国邮路\Debug\中国邮路.ilk

     文件    2713496  2014-07-03 14:48  中国邮路\Debug\中国邮路.pch

     文件    1139712  2014-07-03 15:06  中国邮路\Debug\中国邮路.pdb

     文件      11515  2014-07-03 15:06  中国邮路\main.cpp

     文件       4304  2014-07-03 15:47  中国邮路\中国邮路.dsp

     文件        541  2014-07-03 14:47  中国邮路\中国邮路.dsw

     文件      41984  2014-08-03 16:30  中国邮路\中国邮路.ncb

     文件      48640  2014-08-03 16:30  中国邮路\中国邮路.opt

     文件        250  2014-08-03 16:29  中国邮路\中国邮路.plg

     目录          0  2014-07-03 15:06  中国邮路\Debug

     目录          0  2014-08-03 16:30  中国邮路

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

              5920868                    15