全部资源
全部资源
C/C++
C#
PHP
Java
Python
VB
ASP
Html/CSS
Matlab
JavaScript
数据库
模板
其他

K短路（双扫描法）C++

收藏(0)
  • 大小: 1.41MB
    文件类型: .rar
    金币: 2
    下载: 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个文件信息

评论

共有 条评论

相关资源