数据结构课程设计作业:求任意两点的最短路径问题,写个完整的程序..急求啊...小弟上学期没学好..解决加分谢
更新日期：2024.05.17
一：
#include "stdafx.h"
#include <limits>
#include <iostream>
#include <fstream>
using namespace std;
const int MAXINT = numeric_limits<int>::max();
template <class Type>
void Dijkstra(int n, int v, Type dist[], int prev[], Type** c)
{
bool *s = new bool[n+1];
int i, j;
for(i = 1; i <=n; i++)
{
dist[i] = c[v][i];
if(c[v][i]!=MAXINT)
prev[i] = v;
else prev[i] =0;
s[i] = false;
}
s[v] = true;
dist[v] = 0;
prev[v] = 0;
for(i = 1; i< n; i++)
{
int u = v;
int temp = MAXINT;
for( j = 1; j<=n; j++)
if(!s[j]&&dist[j]<temp)
{
u = j;
temp = dist[j];
}
s[u] = true;
for(j=1; j<=n; j++)
{
if((!s[j])&&c[u][j]<MAXINT)
{
if((dist[u]+c[u][j])<dist[j])
{
dist[j] = dist[u] + c[u][j];
prev[j] = u;
}
}
}
}
delete [] s;
}
void djpath(int m, int v, int prev[])
{
int i = m ,j =1;
while(i!=0)
{
if (j == 1)
{
cout<< i;
j = 0;
}
else
cout<< "-" << i;
i = prev[i];
}
cout<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"最大整数:"<<MAXINT<<endl;
int prev[6], dist[6];
int i,j,n;
int** myc;
FILE *fp;
fp=fopen("data.txt", "r");
fscanf(fp,"%d", &n);
myc = new int* [n+1];
for(i =0; i<=n; i++)
myc[i] = new int[n+1];
for(i=1; i<=n; i++)
for(j =1; j<=n; j++)
{
fscanf(fp, "%d",&myc[i][j]);
if (myc[i][j]==-1)
myc[i][j] = MAXINT;
}
Dijkstra(5, 1, dist, prev, myc);
for(i = 1; i<=5; i++)
cout<<dist[i]<<endl;
for(i=2; i<=5; i++)
djpath(i,1,prev);
for(i = 0; i<=5; i++)
delete[] myc[i];
delete [] myc;
return 0;
}
输入数据采用文本文件格式，下面是data.txt的内容:
5
0 10 -1 30 100
10 0 50 -1 -1
-1 50 0 20 10
30 -1 20 0 60
100 -1 10 60 0
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/mikewolf2009/archive/2009/09/12/4545537.aspx
二：
#include<iostream>
using namespace std;
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;
d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];
for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}
for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t)) {t=d[j];k=j;} //在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
s[k]=1;//point k join the S
for (j=1;j<n;j++) //将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=<s，…，k，j>。且D[j]减小的新路径P只可能是由于路径<s，…，k>和边<k，j>组成。所以，当length(P)=D[k]+w<k，j>小于D[j]时，应该用P的长度来修改D[j]的值。
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}
}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";
}
以上二个代码都是完整可以使用的，楼主喜欢哪个就用那个吧。自己还是可以仔细分析下代码。
就是两个坐标点算距离的吗？
是的话就简单了。
15593636135 :C++数据结构作业,建立全国高铁网络,并求任意两个车站之间的最短路径 类...
冷程侮1299 :答：int ShortPath(MGraph G,int v0,PathMatrix &P,ShortPathTable &D){ //用戴克斯特拉算法求有向图G中v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]。//若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。//final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。fo...
15593636135 :数据结构课程设计作业:求任意两点的最短路径问题,写个完整的程序..急 ...
冷程侮1299 :答：一：include "stdafx.h"include <limits> include <iostream> include <fstream> using namespace std;const int MAXINT = numeric_limits<int>::max();template <class Type> void Dijkstra(int n, int v, Type dist[], int prev[], Type** c){ bool *s = new bool[n+1];int i,...
15593636135 :...寻大神帮助,利用C语言实现:求任意两个集合的交集、并集、差集,_百 ...
冷程侮1299 :答：以前写过一个纯C的， 用的是数组，模拟C++ STL里面的set_intersection，set_union和set_difference的实现。 稍作了修改，添加了些注释，希望能帮到你。注意：必须先对输入集合排序；输出结果和C++ STL的测试结果吻合。include <stdio.h>#include <stdlib.h>#include <string.h>int set_intersection (...
15593636135 :设计一个程序实现两个任意长的整数求和与差的运算
冷程侮1299 :答：2010-01-03 用数据结构算法实现---任意长的整数相加 2 2015-09-02 编写一个程序,要求输入任意个整数,然后对其求和,这个任意个整... 2 更多类似问题 > 正在求助 换一换 回答问题,赢新手礼包 苦等7分钟: 为什么有些人不愿意接受本子 回答 苦等17分钟: 其实不明白为什么有些人可以玩妹调玩得下去 回答...
15593636135 :数据结构课程设计,以顺序存储结构表示串,求两个字符串中的最长公共子...
冷程侮1299 :答：:");gets(T1.ch);printf("输入第二个字符串 :");gets (P1.ch);T1.length=strlen (T1.ch);P1.length=strlen (P1.ch);printf("第一个串为：%s，长度：%d\n",T1.ch,T1.length);printf("第二个串为：%s，长度：%d\n",P1.ch,P1.length);search(T1,P1);} ...
15593636135 :急求求大仙帮忙!C语言数据结构课程设计,关于旅游图。
冷程侮1299 :答：你这个应该是图论编程的大作业吧(1) 图的邻接矩阵和邻接表表示, easy(2) 直接从图的邻接表表示就可以得结果,easy(3) Dijkstra算法,求最短路径,不难。(4) Floyd算法,求任意2点间最短路径,中等难度。(5) 这个属于旅行商问题(TSP),非常难的问题,百度一下,有很多专门的算法。(6) 设计菜单,不会 追问 能...
15593636135 :急!!!数据结构课程设计
冷程侮1299 :答：急!!!数据结构课程设计 对任意给定的图(顶点数不小于20,边数不少于30,图的类型可以是有向图、无向图、有向网、无向网),能够输入图的顶点和边(或弧)的信息,并存储到相应存储结构(邻接矩阵、邻接表、... 对任意给定的图(顶点数不小于20,边数不少于30,图的类型可以是有向图、无向图、有向网、无向网)...
15593636135 :50分急求!!数据结构课程设计,c链表的基本操作和二叉树的几种遍历...
冷程侮1299 :答：1.对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构,并实现二叉树的先序、中序、后序三种遍历,输出三种遍历的结果。 2. 求二叉树高度、结点数、度为1的结点数和叶子结点数。 展开 我来答 1个回答 #热议# 已婚女性就应该承担家里大部分家务吗?djxldy 2010-06-01 · TA获得超过203个赞 ...
15593636135 :《数据结构 课程设计》表达式求值 实验报告
冷程侮1299 :答：2 算术表达式求值演示 一、概述 数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是算术表达式求值...
15593636135 :◆急需◆数据结构课程设计C语言--任意两个高次多项式的乘法运算和加法运...
冷程侮1299 :答：散发出浓郁的春天气息，在你的碧空下到处是爱与狂欢，加法 在通往达玛莱斯科塔的路上。如同绽开的浪花重重。杨柳招摇披绿装，哈哈
#include "stdafx.h"
#include <limits>
#include <iostream>
#include <fstream>
using namespace std;
const int MAXINT = numeric_limits<int>::max();
template <class Type>
void Dijkstra(int n, int v, Type dist[], int prev[], Type** c)
{
bool *s = new bool[n+1];
int i, j;
for(i = 1; i <=n; i++)
{
dist[i] = c[v][i];
if(c[v][i]!=MAXINT)
prev[i] = v;
else prev[i] =0;
s[i] = false;
}
s[v] = true;
dist[v] = 0;
prev[v] = 0;
for(i = 1; i< n; i++)
{
int u = v;
int temp = MAXINT;
for( j = 1; j<=n; j++)
if(!s[j]&&dist[j]<temp)
{
u = j;
temp = dist[j];
}
s[u] = true;
for(j=1; j<=n; j++)
{
if((!s[j])&&c[u][j]<MAXINT)
{
if((dist[u]+c[u][j])<dist[j])
{
dist[j] = dist[u] + c[u][j];
prev[j] = u;
}
}
}
}
delete [] s;
}
void djpath(int m, int v, int prev[])
{
int i = m ,j =1;
while(i!=0)
{
if (j == 1)
{
cout<< i;
j = 0;
}
else
cout<< "-" << i;
i = prev[i];
}
cout<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"最大整数:"<<MAXINT<<endl;
int prev[6], dist[6];
int i,j,n;
int** myc;
FILE *fp;
fp=fopen("data.txt", "r");
fscanf(fp,"%d", &n);
myc = new int* [n+1];
for(i =0; i<=n; i++)
myc[i] = new int[n+1];
for(i=1; i<=n; i++)
for(j =1; j<=n; j++)
{
fscanf(fp, "%d",&myc[i][j]);
if (myc[i][j]==-1)
myc[i][j] = MAXINT;
}
Dijkstra(5, 1, dist, prev, myc);
for(i = 1; i<=5; i++)
cout<<dist[i]<<endl;
for(i=2; i<=5; i++)
djpath(i,1,prev);
for(i = 0; i<=5; i++)
delete[] myc[i];
delete [] myc;
return 0;
}
输入数据采用文本文件格式，下面是data.txt的内容:
5
0 10 -1 30 100
10 0 50 -1 -1
-1 50 0 20 10
30 -1 20 0 60
100 -1 10 60 0
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/mikewolf2009/archive/2009/09/12/4545537.aspx
二：
#include<iostream>
using namespace std;
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;
d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];
for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}
for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t)) {t=d[j];k=j;} //在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
s[k]=1;//point k join the S
for (j=1;j<n;j++) //将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=<s，…，k，j>。且D[j]减小的新路径P只可能是由于路径<s，…，k>和边<k，j>组成。所以，当length(P)=D[k]+w<k，j>小于D[j]时，应该用P的长度来修改D[j]的值。
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}
}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";
}
以上二个代码都是完整可以使用的，楼主喜欢哪个就用那个吧。自己还是可以仔细分析下代码。
就是两个坐标点算距离的吗？
是的话就简单了。
冷程侮1299 :答：int ShortPath(MGraph G,int v0,PathMatrix &P,ShortPathTable &D){ //用戴克斯特拉算法求有向图G中v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]。//若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。//final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。fo...
冷程侮1299 :答：一：include "stdafx.h"include <limits> include <iostream> include <fstream> using namespace std;const int MAXINT = numeric_limits<int>::max();template <class Type> void Dijkstra(int n, int v, Type dist[], int prev[], Type** c){ bool *s = new bool[n+1];int i,...
冷程侮1299 :答：以前写过一个纯C的， 用的是数组，模拟C++ STL里面的set_intersection，set_union和set_difference的实现。 稍作了修改，添加了些注释，希望能帮到你。注意：必须先对输入集合排序；输出结果和C++ STL的测试结果吻合。include <stdio.h>#include <stdlib.h>#include <string.h>int set_intersection (...
冷程侮1299 :答：2010-01-03 用数据结构算法实现---任意长的整数相加 2 2015-09-02 编写一个程序,要求输入任意个整数,然后对其求和,这个任意个整... 2 更多类似问题 > 正在求助 换一换 回答问题,赢新手礼包 苦等7分钟: 为什么有些人不愿意接受本子 回答 苦等17分钟: 其实不明白为什么有些人可以玩妹调玩得下去 回答...
冷程侮1299 :答：:");gets(T1.ch);printf("输入第二个字符串 :");gets (P1.ch);T1.length=strlen (T1.ch);P1.length=strlen (P1.ch);printf("第一个串为：%s，长度：%d\n",T1.ch,T1.length);printf("第二个串为：%s，长度：%d\n",P1.ch,P1.length);search(T1,P1);} ...
冷程侮1299 :答：你这个应该是图论编程的大作业吧(1) 图的邻接矩阵和邻接表表示, easy(2) 直接从图的邻接表表示就可以得结果,easy(3) Dijkstra算法,求最短路径,不难。(4) Floyd算法,求任意2点间最短路径,中等难度。(5) 这个属于旅行商问题(TSP),非常难的问题,百度一下,有很多专门的算法。(6) 设计菜单,不会 追问 能...
冷程侮1299 :答：急!!!数据结构课程设计 对任意给定的图(顶点数不小于20,边数不少于30,图的类型可以是有向图、无向图、有向网、无向网),能够输入图的顶点和边(或弧)的信息,并存储到相应存储结构(邻接矩阵、邻接表、... 对任意给定的图(顶点数不小于20,边数不少于30,图的类型可以是有向图、无向图、有向网、无向网)...
冷程侮1299 :答：1.对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构,并实现二叉树的先序、中序、后序三种遍历,输出三种遍历的结果。 2. 求二叉树高度、结点数、度为1的结点数和叶子结点数。 展开 我来答 1个回答 #热议# 已婚女性就应该承担家里大部分家务吗?djxldy 2010-06-01 · TA获得超过203个赞 ...
冷程侮1299 :答：2 算术表达式求值演示 一、概述 数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是算术表达式求值...
冷程侮1299 :答：散发出浓郁的春天气息，在你的碧空下到处是爱与狂欢，加法 在通往达玛莱斯科塔的路上。如同绽开的浪花重重。杨柳招摇披绿装，哈哈
