求c++ 程序 网络上两点间的最短路径
作者&投稿：时苛 （若有异议请与网页底部的电邮联系）
穷举吧 ！
具体要求可以发给我看看
/** File: shortest.c
* Description: 网络中两点最短路径 Dijkstra 算法
* Shortest Path Dijkstra Algorithm
* Created: 2001/11/25
* Author: Justin Hou [mailto:justin_hou@hotmail.com]
*/
#include <stdio.h>
#define true 1
#define false 0
#define I 9999 /* 无穷大 */
#define N 20 /* 城市顶点的数目 */
int cost[N][N] = {
{0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},
{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},
{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},
{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},
{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},
{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},
{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},
{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},
{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},
{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},
{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},
{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}
};
int dist[N]; /* 存储当前最短路径长度 */
int v0 = 'A' - 65; /* 初始点是 A */
void main()
{
int final[N], i, v, w, min;
/* 初始化最短路径长度数据，所有数据都不是最终数据 */
for (v = 0; v < N; v++) {
final[v] = false;
dist[v] = cost[v0][v];
}
/* 首先选v0到v0的距离一定最短，最终数据 */
final[v0] = true;
/* 寻找另外 N-1 个结点 */
for (i = 0; i < N-1; i++) {
min = I; /* 初始最短长度无穷大 */
/* 寻找最短的边 */
for (w = 0; w < N; w++) {
if (!final[w] && dist[w] < min) {
min = dist[w];
v = w;
}
}
final[v] = true; /* 加入新边 */
for (w = 0; w < N; w++) { /* 更新 dist[] 数据 */
if (!final[w] && dist[v] + cost[v][w] < dist[w]) {
dist[w] = dist[v] + cost[v][w];
}
}
}
for (i = 0; i < N; i++) { /* 显示到监视器 */
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}
});
if (left == NULL || right == NULL) {
fprintf(stderr,"Error malloc.\n");
exit(-1);
}
/* 初始化左右分枝结点 */
left->bound = root.bound; /* 继承父结点的下界 */
left->matrix = LeftNode(root.matrix, selectedEdge); /* 删掉分枝边 */
left->path = root.path; /* 继承父结点的路径，没有增加新边 */
left->left = NULL;
left->right = NULL;
right->bound = root.bound;
right->matrix = RightNode(root.matrix, selectedEdge, root.path);/* 删除行列和回路边 */
right->path = AddEdge(selectedEdge, root.path); /* 加入所选边 */
right->left = NULL;
right->right = NULL;
/* 归约左右分枝结点 */
left->bound += Simplify(&left->matrix);
right->bound += Simplify(&right->matrix);
/* 链接到根 */
root.left = left;
root.right = right;
/* 显示到监视器 */
puts("Right Branch:\n------------");
ShowMatrix(right->matrix);
puts("Left Branch:\n-----------");
ShowMatrix(left->matrix);
/* 如果右结点下界小于当前最佳答案，继续分枝搜索 */
if (right->bound < minDist) {
BABA(*right);
}
/* 否则不搜索，因为这条枝已经不可能产生更佳路线 */
else {
printf("Current minDist is %d, ", minDist);
printf("Right Branch's Bound(= %d).\n", right->bound);
printf("This branch is dead.\n");
}
/* 如果右结点下界小于当前最佳答案，继续分枝搜索 */
if (left->bound < minDist) {
BABA(*left);
}
/* 否则不搜索，因为这条枝已经不可能产生更佳路线 */
else {
printf("Current minDist is %d, ", minDist);
printf("Left Branch's Bound(= %d).\n", left->bound);
printf("This branch is dead.\n");
}
printf("The best answer now is %d\n", minDist);
return (minPath);
}
/* 修补路径 */
PATH MendPath(PATH path, MATRIX c)
{
int row, col;
EDGE edge;
int n = c.citiesNumber;
for (row = 0; row < n; row++) {
edge.head = row;
for (col = 0; col < n; col++) {
edge.tail = col;
if (c.distance[row][col] == 0) {
path = AddEdge(edge, path);
}
}
}
return path;
}
/* 归约费用矩阵，返回费用矩阵的归约常数 */
int Simplify(MATRIX* c)
{
int row, col, min_dist, h;
int n = c->citiesNumber;
h = 0;
/* 行归约 */
for (row = 0; row < n; row++) {
/* 找出本行最小的元素 */
min_dist = INFINITY;
for (col = 0; col < n; col++) {
if (c->distance[row][col] < min_dist) {
min_dist = c->distance[row][col];
}
}
/* 如果本行元素都是无穷，说明本行已经被删除 */
if (min_dist == INFINITY) continue;
/* 本行每元素减去最小元素 */
for (col = 0; col < n; col++) {
if (c->distance[row][col] != INFINITY) {
c->distance[row][col] -= min_dist;
}
}
/* 计算归约常数 */
h += min_dist;
}
/* 列归约 */
for (col = 0; col < n; col++) {
/* 找出本列最小的元素 */
min_dist = INFINITY;
for (row = 0; row < n; row++) {
if (c->distance[row][col] < min_dist) {
min_dist = c->distance[row][col];
}
}
/* 如果本列元素都是无穷，说明本列已经被删除 */
if (min_dist == INFINITY) continue;
/* 本列元素减去最小元素 */
for (row = 0; row < n; row++) {
if (c->distance[row][col] != INFINITY) {
c->distance[row][col] -= min_dist;
}
}
/* 计算归约常数 */
h += min_dist;
}
return (h);
}
/* 搜索所有花费为零的边中最合适的，使左枝下界更大 */
EDGE SelectBestEdge(MATRIX c)
{
int row, col;
int n = c.citiesNumber;
int maxD;
EDGE best, edge;
/* 所用函数声明 */
int D(MATRIX, EDGE);
maxD = 0;
for (row = 0; row < n; row++) {
for (col = 0; col < n; col++) {
edge.head = row;
edge.tail = col;
if (!c.distance[row][col] && maxD < D(c, edge)) {
maxD = D(c, edge);
best = edge;
}
}
}
return (best);
}
/* 计算如果选 edge 作为分枝边，左枝（不含 edge）下界的增量 */
int D(MATRIX c, EDGE edge)
{
int row, col, dRow, dCol;
int n = c.citiesNumber;
dRow = INFINITY;
for (col = 0; col < n; col++) {
if (dRow < c.distance[edge.head][col] && col != edge.tail) {
dRow = c.distance[edge.head][col];
}
}
dCol = INFINITY;
for (row = 0; row < n; row++) {
if (dCol < c.distance[row][edge.tail] && row != edge.head) {
dCol = c.distance[row][edge.tail];
}
}
return (dRow + dCol);
}
/* 删掉所选分枝边 */
MATRIX LeftNode(MATRIX c, EDGE edge)
{
c.distance[edge.head][edge.tail] = INFINITY;
return c;
}
/* 删除行列和回路边后的矩阵 */
MATRIX RightNode(MATRIX c, EDGE edge, PATH path)
{
int row, col;
int n = c.citiesNumber;
EDGE loopEdge;
/* 声明所需要的求回路边函数 */
EDGE LoopEdge(PATH, EDGE);
for (col = 0; col < n; col++)
c.distance[edge.head][col] = INFINITY;
for (row = 0; row < n; row++)
c.distance[row][edge.tail] = INFINITY;
loopEdge = LoopEdge(path, edge);
c.distance[loopEdge.head][loopEdge.tail] = INFINITY;
return (c);
}
/* 计算回路边的函数
* 除了加入的新边， 当前结点路线集合中还可能包含一些已经选定的边， 这些边构成一条或
* 几条路径， 为了不构成回路， 必须使其中包含新边的路径头尾不能相连，本函数返回这个
* 头尾相连的边，以便把这个回路边的长度设成无穷。
*/
EDGE LoopEdge(PATH path, EDGE edge)
{
int i, j;
EDGE loopEdge;
/* 最小的回路边 */
loopEdge.head = edge.tail;
loopEdge.tail = edge.head;
/* 寻找回路边的头端点，即包含新边的路径的尾端点 */
for (i = 0; i < path.edgesNumber; i++) {
for (j = 0; j < path.edgesNumber; j++) {
if (loopEdge.head == path.edge[j].head) {
/* 扩大回路边 */
loopEdge.head = path.edge[j].tail;
break;
}
}
}
/* 寻找回路边的尾端点，即包含新边的路径的头端点 */
for (i = 0; i < path.edgesNumber; i++) {
for (j = 0; j < path.edgesNumber; j++) {
if (loopEdge.tail == path.edge[j].tail) {
/* 扩大回路边 */
loopEdge.tail = path.edge[j].head;
break;
}
}
}
return (loopEdge);
}
/* 将新边加入到路径中 */
PATH AddEdge(EDGE edge, PATH path)
{
path.edge[path.edgesNumber++] = edge;
return path;
}
/* 计算花费矩阵当前阶数 */
int MatrixSize(MATRIX c, PATH path)
{
return (c.citiesNumber - path.edgesNumber);
}
/* 显示路径 */
void ShowPath(PATH path, MATRIX c)
{
int i, dist;
EDGE edge;
int n = path.edgesNumber;
dist = 0;
printf("\nThe path is: ");
for (i = 0; i < n; i++) {
edge = path.edge[i];
printf("(%d, %d) ", edge.head + 1, edge.tail + 1);
dist += c.distance[edge.head][edge.tail];
}
/* printf("[Total Cost: %d]\n", dist); */
}
/* 显示花费矩阵 */
void ShowMatrix(MATRIX c)
{
int row, col;
int n = c.citiesNumber;
for (row = 0; row < n; row++) {
for (col = 0; col < n; col++) {
if (c.distance[row][col] != INFINITY) {
printf("%3d", c.distance[row][col]);
}
else {
printf(" -");
}
}
putchar('\n');
}
getch();
}
由于程序太长，直接传给你了。下面是主程序。
void main()
{
dijkstra s;
s.read();
s.algorithm();
s.output();
}
直线不是最短的，虫洞才是最短的。
我不会但是我想要你的分看你给不给了。
象肿苏合： #includetypedef int ElemType; typedef struct LNode { ElemType date; struct LNode *next; }linklist,*link; /*构造链表*////////////////////////////////////// void IinitList(link &L) { if(L)delete L; L= (link)malloc(sizeof(LNode)) ; if (!L) exit(1); L->next=NULL; cout} ////////////...
梁山县15780899080： C++问题 计算两点之间的距离 - ？
象肿苏合： #include <cmath> #include <iostream> using namespace std; int main(){ float x1,y1,x2,y2,s; cout <<＂输入<x1,y1> <x2,y2>:\n＂; cin>>x1>>y1>>x2>>y2; s=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//2次开根号函数,必须包含头文件cmath. cout <<＂两点之间的距离为:＂<<s<<endl; return 0; }
梁山县15780899080： 用C++设计一个类求两点间的距离? - ？
象肿苏合： #include struct POINT { double x; double y; }; double dist(POINT a,POINT b) { double dis = 0.0; dis = sqrt(pow(fabs(a.x - b.x)) + pow(fabs(a.y - b.y))); }
梁山县15780899080： C++编程 求两个浮点数的点间距离 - ？
象肿苏合： #include void main() { float x1,y1,x2,y2; double distance; cout cin>>x1>>y1>>x2>>y2; distance=sqrt(pow((x1-x2),2)+pow((y1-y2),2)); cout}
梁山县15780899080： c++MFC里面求两点之间的距离是什么函数,不是sqrt - ？
象肿苏合： 自己根据两点坐标算出来..distance = sqrt((x1-x2)(x1-x2) + (y1-y2)(y1-y2))
梁山县15780899080： C++ 求两点间的距离 - ？
象肿苏合： #include#includeusing namespace std; struct point { double x; double y; }; double getr(struct point p) { double d; d=sqrt(p.x*p.x+p.y*p.y); return d; } int main( ) { double d; struct point data; cout>data.x; cin>>data.y; d=getr(data); cout
梁山县15780899080： C++用类实现计算两点之间的距离. - ？
象肿苏合： #include using namespace std; int main(){ float x1,y1,x2,y2,s; cout <<＂输入 :\n＂; cin>>x1>>y1>>x2>>y2; s=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//2次开根号函数,必须包含头文件cmath. cout <<＂两点之间的距离为:＂<< return 0; }
梁山县15780899080： 要求用C++语言随机生成一个n个顶点有向强连通图,然后求出图的两两顶点之间的最短距离.求高手解答啊! - ？
象肿苏合： 单元最短路径~
梁山县15780899080： c++求两个点距离问题 新手求指教 多谢多谢 - ？
象肿苏合： 可以以0点为原点,将0-13共14个点的坐标用数组(二维)存放,然后二重循环,求每个点到其他点的距离,结果也可以保存到一个二维数组A[14][14]中,输出时只需要查A[M][N]即可得到点M到点N的距离
梁山县15780899080： c++求两点间的距离,跪求大神指导 - ？
象肿苏合： 这位同学应该是大一的新生吧,作为这个时候我感觉给你直接指出代码中的错误对你来说也没太大帮助,你应该仔细看看C++中类那个章节,关于构造函数,关于类的使用.第一,在你这个代码里面,你的代码p1.Point(),p2.Point()这两行代码...
