上传源码
  1. 首页
  2. C/C++

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

标签： KSP C++  • 文件类型: .rar • 文件大小: 1.41MB • 下载次数: 1 •

使用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-doublesweepalgorithm7K·__15848_.doc

     文件     137216  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestDebugK_shortest.exe

     文件     640300  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestDebugK_shortest.ilk

     文件    1240064  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestDebugK_shortest.pdb

     目录          0  2010-09-07 15:10  KSP-doublesweepalgorithmK_shortestDebug

     文件       7398  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestK_shortestDebugBuildLog.htm

     文件     508518  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestK_shortestDebuggraph_process.obj

     文件        663  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestK_shortestDebugK_shortest.exe.embed.manifest

     文件        728  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestK_shortestDebugK_shortest.exe.embed.manifest.res

     文件        621  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestK_shortestDebugK_shortest.exe.intermediate.manifest

     文件      28399  2010-09-04 20:06  KSP-doublesweepalgorithmK_shortestK_shortestDebugK_shortest.obj

     文件    3211264  2010-09-04 20:05  KSP-doublesweepalgorithmK_shortestK_shortestDebugK_shortest.pch

     文件         65  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestK_shortestDebugmt.dep

     文件      12321  2010-09-04 20:05  KSP-doublesweepalgorithmK_shortestK_shortestDebugstdafx.obj

     文件     314368  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestK_shortestDebugvc90.idb

     文件     339968  2010-09-04 20:13  KSP-doublesweepalgorithmK_shortestK_shortestDebugvc90.pdb

     目录          0  2010-09-07 15:10  KSP-doublesweepalgorithmK_shortestK_shortestDebug

     文件       6389  2010-09-04 20:38  KSP-doublesweepalgorithmK_shortestK_shortestgraph_process.cpp

     文件       1769  2010-09-05 16:25  KSP-doublesweepalgorithmK_shortestK_shortestheader.h

     文件        347  2010-09-04 20:05  KSP-doublesweepalgorithmK_shortestK_shortestK_shortest.cpp

     文件       4654  2010-09-04 20:05  KSP-doublesweepalgorithmK_shortestK_shortestK_shortest.vcproj

     文件       1411  2010-09-04 21:32  KSP-doublesweepalgorithmK_shortestK_shortestK_shortest.vcproj.huan-PC.huan.user

     文件       1320  2010-09-04 10:13  KSP-doublesweepalgorithmK_shortestK_shortestReadMe.txt

     文件        297  2010-09-04 10:13  KSP-doublesweepalgorithmK_shortestK_shorteststdafx.cpp

     文件        320  2010-09-04 10:13  KSP-doublesweepalgorithmK_shortestK_shorteststdafx.h

     文件        765  2010-09-04 10:13  KSP-doublesweepalgorithmK_shortestK_shortest argetver.h

     目录          0  2010-09-07 15:10  KSP-doublesweepalgorithmK_shortestK_shortest

     文件    3656704  2010-09-04 21:32  KSP-doublesweepalgorithmK_shortestK_shortest.ncb

     文件        896  2010-09-04 10:13  KSP-doublesweepalgorithmK_shortestK_shortest.sln

    ..A..H.     12288  2010-09-04 21:32  KSP-doublesweepalgorithmK_shortestK_shortest.suo

............此处省略6个文件信息
立即下载
计算机网络课程设计 IP数据报的捕获和解析   snake算法的C++代码
0 0

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件举报，一经查实，本站将立刻删除。

发表评论

评论列表（条）