• 大小: 1.41MB
    文件类型: .rar
    金币: 1
    下载: 0 次
    发布日期: 2023-10-21
  • 语言: C/C++
  • 标签: KSP  C++  

资源简介

使用C++ 编写的K短路计算方法,基于先进的双扫描法(doublesweep),效率较高

资源截图

代码片段和文件信息


#pragma  once 

#include “stdafx.h“
#include “header.h“
#include 
#include 


Graph::Graph(){

}

Graph::~Graph(){
delete []matrixVector;

}

void Graph::graphRead(){
cout<<“Please input the number of the graph nodes:“< cin>>graphNode;
cout<<“Please input the K:“< cin>>kPathnumber;

graph = new double*[graphNode];

for(int i = 0 ; i < graphNode ; i ++)
graph[i] = new double[graphNode];

for(int i = 0 ; i  < graphNode ; i ++)
for(int j = 0 ; j < graphNode ; j ++)
cin>>graph[i][j];

cout<<“Please input the Start Point:“< cin>>startPoint ;
cout<<“Please input the End Point:“< cin>>endPoint;

}

void Graph::findShortestPath(){
shortestPath = new double*[graphNode];

for(int i = 0 ; i < graphNode ; i ++)
shortestPath[i] = new double[graphNode];

for(int i = 0 ; i  < graphNode ; i ++)
for(int j = 0; j < graphNode ; j ++){
if(graph[i][j]!= 0.0)
shortestPath[i][j] = graph[i][j];
else
    shortestPath[i][j] = MAXNUMBER;
}

for(int k = 0 ; k < graphNode ; k ++){                //Floyd algorithm to compute the shortest path 
for(int i = 0 ; i < graphNode ; i ++){
for(int j = 0 ; j < graphNode ; j ++){
if(shortestPath[i][j] > shortestPath[i][k] + shortestPath[k][j])
shortestPath[i][j] = shortestPath[i][k] + shortestPath[k][j];
}
}
}

matrixVector = new KShort[graphNode * graphNode];
for(int i = 0 ; i < graphNode ; i ++){
for(int j = 0 ; j < graphNode ; j ++){
if(i == j)
matrixVector[i * graphNode + j].Dis.push_back(0.0);
else {
matrixVector[i * graphNode + j].Dis.push_back(shortestPath[i][j]);
for(int k = 1 ; k < kPathnumber ; k ++)
matrixVector[i * graphNode + j].Dis.push_back(MAXNUMBER);
}
}
}

}

int Graph::judge(KShort *A  KShort *B){                             //judge to terminate

int flag = 0;

for(int i = 0 ; i < graphNode ; i ++){
if(flag)
break;
for(int j = 0 ; j < kPathnumber ; j ++)
if(A[i].Dis.at(j) != B[i].Dis.at(j)){
flag = 1;
break;
}
}

return flag;

}


Graph::KShort Graph::vectorAdd(Graph::KShort A Graph::KShort B){
KShort ans ;
double *tmp;
tmp = new double[A.Dis.size() + B.Dis.size()];
int size = 0;

mapmp;

mp.clear();

for(vector::iterator it = A.Dis.begin() ; it != A.Dis.end() ; it ++){
tmp[size] = (*it);
mp[(*it)] = 1;
size ++;
}

for(vector::iterator it = B.Dis.begin() ; it != B.Dis.end() ; it ++){
if(mp[(*it)] == 0){
tmp[size] = (*it);
mp[(*it)] = 1;
size ++;
}

}

qsort(tmp  size  sizeof(double)  cmp);

for(int i = 0 ; i < kPathnumber ; i ++)
ans.Dis.push_back(tmp[i]);

return ans;
}

Graph::KShort Graph::vectorMulty(KShort A  KShort B){
KShort ans; 
double *tmp;
mapmp;
mp.clear();

tmp = new double[A.Dis.size() * B.Dis.size()];

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

     文件     104448  2010-09-04 10:07  KSP-doublesweep\algorithm\07K·__15848_.doc

     文件     137216  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\Debug\K_shortest.exe

     文件     640300  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\Debug\K_shortest.ilk

     文件    1240064  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\Debug\K_shortest.pdb

     目录          0  2010-09-07 15:10  KSP-doublesweep\algorithm\K_shortest\Debug

     文件       7398  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\BuildLog.htm

     文件     508518  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\graph_process.obj

     文件        663  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\K_shortest.exe.embed.manifest

     文件        728  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\K_shortest.exe.embed.manifest.res

     文件        621  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\K_shortest.exe.intermediate.manifest

     文件      28399  2010-09-04 20:06  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\K_shortest.obj

     文件    3211264  2010-09-04 20:05  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\K_shortest.pch

     文件         65  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\mt.dep

     文件      12321  2010-09-04 20:05  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\stdafx.obj

     文件     314368  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\vc90.idb

     文件     339968  2010-09-04 20:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug\vc90.pdb

     目录          0  2010-09-07 15:10  KSP-doublesweep\algorithm\K_shortest\K_shortest\Debug

     文件       6389  2010-09-04 20:38  KSP-doublesweep\algorithm\K_shortest\K_shortest\graph_process.cpp

     文件       1769  2010-09-05 16:25  KSP-doublesweep\algorithm\K_shortest\K_shortest\header.h

     文件        347  2010-09-04 20:05  KSP-doublesweep\algorithm\K_shortest\K_shortest\K_shortest.cpp

     文件       4654  2010-09-04 20:05  KSP-doublesweep\algorithm\K_shortest\K_shortest\K_shortest.vcproj

     文件       1411  2010-09-04 21:32  KSP-doublesweep\algorithm\K_shortest\K_shortest\K_shortest.vcproj.huan-PC.huan.user

     文件       1320  2010-09-04 10:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\ReadMe.txt

     文件        297  2010-09-04 10:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\stdafx.cpp

     文件        320  2010-09-04 10:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\stdafx.h

     文件        765  2010-09-04 10:13  KSP-doublesweep\algorithm\K_shortest\K_shortest\targetver.h

     目录          0  2010-09-07 15:10  KSP-doublesweep\algorithm\K_shortest\K_shortest

     文件    3656704  2010-09-04 21:32  KSP-doublesweep\algorithm\K_shortest\K_shortest.ncb

     文件        896  2010-09-04 10:13  KSP-doublesweep\algorithm\K_shortest\K_shortest.sln

    ..A..H.     12288  2010-09-04 21:32  KSP-doublesweep\algorithm\K_shortest\K_shortest.suo

............此处省略6个文件信息

评论

共有 条评论