数据结构上机题4 最短路径
2017-12-09
最短路
题目
ddl：12月9日。
实验题目：
- 给定图的边和边权值（非负数），求给定两顶点间的最短路径。边和边权值（格式为边的兩顶点和权值，勿直接输入邻接矩阵）、两顶点由窗口（文件也可以）输入。输出路径和路径总权值。
基本要求（8分）：
- 无向图、顶点以自然数命名
扩展：
- 有向图；
- 路径除起终顶点外，过另外几个给定顶点；
- 顶点支持隨意命名；
- 图形界面；
- 等等….
说明
1.打开ShortestPaths.exe，选择有向图模式或无向图模式
2.点击帮助按钮查看如何操作
3.点击导入文件可导入事先建好的图，.udg为无向图文件，.dg为有向图文件，只能导入运行程序目录下的文件，只输入文件名（不用输入后缀名，会根据当前模式读取对应文件）
4.导入后，左键单击某个顶，呈选中状态（绿色），然后按住SHIFT，再左键单击另一个顶，将求出最短路径，路径高亮加粗显示（黄色）。
5.ShortestPaths文件夹内为工程源代码，在VS2010下创建，ShortestPaths.cpp绘制界面和处理键鼠操作，graph.h为图数据结构声明和基本操作
截图
代码
注：需要easyx图形库
graph.h
#include <string.h>
#define INF 99999999
#define MAX_VERTEX_NUM 100
#define MAX_NAME 10
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define Status int
typedef enum {DG,DN,UDG,UDN}GraphType;
typedef struct ArcCell{
int w;//边的权值,0为不连通
}GArc,ArcArray[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct Vertex{
TCHAR name[MAX_NAME];//顶的名称
int x,y;//用于绘制该顶时的位置
int l;//dijkstra算法需要
int state;//=0正常，=1选中
}GVex,VexArray[MAX_VERTEX_NUM];
typedef struct Graph{
ArcArray arcs;
VexArray vexs;
int arcnum,vexnum;
GraphType type;
}MGraph;
typedef struct DijkstraResult{
int vexbegin;//表示这个结果是从该顶到其他顶的最短距离
int prev[MAX_VERTEX_NUM];//最短路径上每个顶的前一个顶
int dist[MAX_VERTEX_NUM];//每个顶到vexbegin的最短距离
}DijRes;
Status CreateGraph(MGraph* g){
g->arcnum=0;
g->vexnum=0;
memset(g->vexs,0,sizeof(GVex)*MAX_VERTEX_NUM);
memset(g->arcs,0,sizeof(GArc)*MAX_VERTEX_NUM*MAX_VERTEX_NUM);
return OK;
}
Status DestoryGraph(MGraph *g){
g->arcnum=0;
g->vexnum=0;
memset(g->vexs,0,sizeof(GVex)*MAX_VERTEX_NUM);
memset(g->arcs,0,sizeof(GArc)*MAX_VERTEX_NUM*MAX_VERTEX_NUM);
return OK;
}
int LocateVex(MGraph g,TCHAR vexname[]){//获取顶在图中的位置，即在顶数组中的下标,未找到返回-1
int i;
for(i=0;i<g.vexnum;i++){
if(!_tcscmp(g.vexs[i].name,vexname)) return i;
}
return -1;
}
Status InsertVex(MGraph *g,TCHAR vexname[],int x,int y){//添加一个顶，不允许为空，不允许重名
_tcscpy_s(g->vexs[g->vexnum].name,vexname);
g->vexs[g->vexnum].x=x;
g->vexs[g->vexnum].y=y;
g->vexs[g->vexnum].l=0;
g->vexnum++;
return OK;
}
Status DeleteVex(MGraph *g,TCHAR vexname[]){
int i=LocateVex(*g,vexname),j;
if(i==-1) return ERROR;
_tcscpy_s(g->vexs[i].name,g->vexs[g->vexnum-1].name);//最后一个顶覆盖要删除的顶
_tcscpy_s(g->vexs[g->vexnum-1].name,_T(""));
for(j=0;j<MAX_VERTEX_NUM;j++){
g->arcs[i][j].w=g->arcs[g->vexnum-1][j].w;
g->arcs[g->vexnum-1][j].w=0;
}
return OK;
}
DijRes Dijkstra(MGraph g,int v){//求其他各顶到顶v的最短路径
DijRes r={};
int flag[MAX_VERTEX_NUM]={0};//标志是否已找到最短路径
int i,j,mindist,minu;
for(i=0;i<g.vexnum;i++){//初始化每个顶到v的距离
if(g.arcs[v][i].w){//连通则初始距离为边权
r.dist[i]=g.arcs[v][i].w;
r.prev[i]=v;
}
else{//不连通为无穷
r.dist[i]=INF;
r.prev[i]=-1;
}
}
r.dist[v]=0;//v到v为0
flag[v]=1;//v标志为已找到
for(i=1;i<g.vexnum;i++){//遍历vexnum-1次,每次找出一个顶点的最短路径
mindist=INF+1;
minu=-1;
for (j=0;j<g.vexnum;j++){//求出未标记的顶中到v最短的
if(flag[j]==0 && r.dist[j]<mindist){
mindist=r.dist[j];
minu=j;
}
}
flag[minu]=1;
for (j=0;j<g.vexnum;j++){//根据新找到的顶u更新其他各顶最短距离
int sum=mindist+(g.arcs[minu][j].w==0?INF:g.arcs[minu][j].w); // 边权为0不连通，以无穷计算
if (flag[j]==0 && (sum<r.dist[j])){
r.dist[j]=sum;
r.prev[j]=minu;
}
}
}
return r;
}
ShortestPaths.cpp
// MinRoad.cpp : 定义控制台应用程序的入口点。
#define SPACE 20 //按钮间隔大小
#define HEIGHT 480
#define WIDTH 800
#define BUTTONHEIGHT 40 //按钮大小
#define BUTTONWIDTH 150 //按钮大小
#define CONTROLWIDTH BUTTONWIDTH+2*SPACE //控制区大小
#define VEXRADIUS 20 //顶半径
#define ARROWLEN 10 //箭头斜边的长
#define PI 3.1415926
#define HPI 1.5707963
#include <graphics.h>//easyx图形库头文件
#include <windows.h>
#include <stdio.h>
#include <math.h>
#include "graph.h"//图
TCHAR runpath[256];//运行路径
int MODE=0;//0为无向图，1为有向图
int vsel=-1;//当前选中顶
int vmov=-1;//当前移动顶
MGraph g;//定义一个图
void DrawButton(int left,int top,LPCTSTR text){
setbkmode(TRANSPARENT);//设置字体背景透明
setfillcolor(RGB(136,247,104));//设置填充颜色
setlinestyle(PS_SOLID,4);//设置线型线宽
setlinecolor(RGB(249,102,102));//设置线颜色
settextstyle(25, 0, _T("宋体"),0,0,FW_BOLD,0,0,0);//设置字体，大小，粗细
settextcolor(RGB(0,0,255));//设置字体颜色
RECT r;
r.left=left; r.top=top; r.right=left+BUTTONWIDTH; r.bottom=top+BUTTONHEIGHT;
fillroundrect(left,top,left+BUTTONWIDTH,top+BUTTONHEIGHT,5,5);//带边框填充
drawtext(text,&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);//输出字
}
void InitUI(){
initgraph(WIDTH, HEIGHT); // 创建绘图窗口
int t=SPACE;
DrawButton(SPACE,t,(LPCTSTR)L"帮 助");
t+=SPACE+BUTTONHEIGHT;
DrawButton(SPACE,t,(LPCTSTR)L"导出文件");
t+=SPACE+BUTTONHEIGHT;
DrawButton(SPACE,t,(LPCTSTR)L"导入文件");
t+=SPACE+BUTTONHEIGHT;
DrawButton(SPACE,t,(LPCTSTR)L"关 于");
line(CONTROLWIDTH,0,CONTROLWIDTH,HEIGHT);
HRGN rgn = CreateRectRgn(CONTROLWIDTH,0,WIDTH,HEIGHT);
setcliprgn(rgn);//之后的绘图区域只在该矩形内有效
DeleteObject(rgn);
}
void DrawVex(int i){
setbkmode(TRANSPARENT);//设置字体背景透明
setfillcolor(RGB(255,188,121));//设置填充颜色
setlinestyle(PS_SOLID,4);//设置线型线宽
if(g.vexs[i].state==0)
setlinecolor(RGB(129,29,228));//设置线颜色
else
setlinecolor(RGB(92,185,0));//设置线颜色(选中状态)
settextstyle(30, 0, _T("Arial"),0,0,FW_BOLD+100,0,0,0);//设置字体，大小，粗细
settextcolor(RGB(255,0,0));//设置字体颜色
RECT r;
r.left=g.vexs[i].x-VEXRADIUS; r.top=g.vexs[i].y-VEXRADIUS;
r.right=g.vexs[i].x+VEXRADIUS; r.bottom=g.vexs[i].y+VEXRADIUS;
fillcircle(g.vexs[i].x,g.vexs[i].y,VEXRADIUS);
drawtext((LPCTSTR)(g.vexs[i].name),&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
}
double GetAngle(int x1,int y1,int x2,int y2){//从(x1,y1)到(x2,y2)的向量的方位角，以x轴为0度，顺时针，弧度值
double a=atan(((double)(y2-y1))/(x2-x1));//得到-pi/2~pi/2的弧度值
if(x2>x1) return a;
else if(x2==x1) return (y2>=y1)?HPI:-HPI;//pi/2和-pi/2,两点重合这里会返回pi/2
else return (y2>=y1)?a+PI:a-PI;
}
void DrawArc(int i,int j,int mode,int inroad){//画边;mode=0,无向;mode=1,有向,i到j;inroad=1则换一种颜色画边
if(!inroad){
setlinestyle(PS_SOLID,3);//设置线型线宽
setlinecolor(RGB(0,196,166));//设置线颜色
}
else{
setlinestyle(PS_SOLID,4);//设置线型线宽
setlinecolor(RGB(255,250,28));//设置线颜色
}
settextstyle(23, 0, _T("Arial"),0,0,FW_BOLD,0,0,0);//设置字体，大小，粗细
TCHAR tw[10]={};
_stprintf_s(tw,_T("%d"),g.arcs[i][j].w);//即使对于无向图也通用，因为arcs[i][j]和arcs[j][i]一样
if(!mode){//无向图，直接连线
line(g.vexs[i].x,g.vexs[i].y,g.vexs[j].x,g.vexs[j].y);
outtextxy((g.vexs[i].x+g.vexs[j].x)/2,(g.vexs[i].y+g.vexs[j].y)/2,tw);
}
else{//有向图，画边时两个方向的线需要错开，不重叠，并且带箭头
double a=GetAngle(g.vexs[i].x,g.vexs[i].y,g.vexs[j].x,g.vexs[j].y);//从顶i到j的向量的方位角
double da=30.0/180.0*PI;//30度角对应的弧度,
int x1=g.vexs[i].x+cos(a-da)*VEXRADIUS,y1=g.vexs[i].y+sin(a-da)*VEXRADIUS;
int x2=g.vexs[j].x+cos(a+da-PI)*VEXRADIUS,y2=g.vexs[j].y+sin(a+da-PI)*VEXRADIUS;
line(x1,y1,x2,y2);//画i到j的边的直线,下面画箭头
double len1_2=sqrt(pow((long double)(g.vexs[i].x-g.vexs[j].x),2)+pow((long double)(g.vexs[i].y-g.vexs[j].y),2))/2;//该边1/2长
int arrx=x1+len1_2*cos(a),arry=y1+len1_2*sin(a);//箭头端点所在坐标
double db=2.617994;//150度角对应的弧度
line(arrx,arry,arrx+cos(a-db)*ARROWLEN,arry+sin(a-db)*ARROWLEN);//箭头一侧边
line(arrx,arry,arrx+cos(a+db)*ARROWLEN,arry+sin(a+db)*ARROWLEN);//箭头一侧边
outtextxy((x1+x2)/2,(y1+y2)/2,tw);
}
}
void DrawMGraph(){
clearcliprgn();//清空绘图区
int i,j;
for(i=0;i<g.vexnum;i++){//先画边，再画顶不然边会部分叠在顶上
for(j=0;j<g.vexnum;j++){
if(g.arcs[i][j].w) DrawArc(i,j,MODE,0);
}
}
for(i=0;i<g.vexnum;i++){
DrawVex(i);
}
}
void OnButtonClick(int i){
FILE* fp;
TCHAR filename[32]=_T("test");
TCHAR filepath[256];
switch(i){
case 1: MessageBox(GetHWnd(),_T(\
"1.点击空白处添加新顶.\n2.在某顶上按住右键可移动该顶.\n3.左键单击某个顶可以选中.\n4.选中某顶后,ctrl+左键单击另一顶可添加边.\n5.选中某顶后,shift+左键单击另一顶可求最短路径."\
),_T("Help"),MB_OK|MB_ICONINFORMATION);
break;
case 2: if(InputBox(filename,32,_T("文件将保存在当前运行目录下，无向图后缀名为.udg，有向图后缀名为.dg\n请输入文件名(不带后缀名):"),_T("保存文件"),(LPCTSTR)filename,0,0,0)){
_stprintf_s(filepath,_T("%s%s%s"),runpath,filename,MODE?_T(".dg"):_T(".udg"));//生成保存路径
if(!_tfopen_s(&fp,filepath,_T("wb+"))){
fwrite(&g,sizeof(g),1,fp);
fclose(fp);
MessageBox(GetHWnd(),_T("导出成功！"),_T("提示"),MB_OK|MB_ICONINFORMATION);
}
else{
MessageBox(GetHWnd(),_T("文件不存在！！"),_T("错误"),MB_OK|MB_ICONWARNING);
}
}
break;
case 3: if(InputBox(filename,32,_T("将打开当前运行目录下的文件，无向图后缀名为.udg，有向图后缀名为.dg\n请输入文件名(不带后缀名):"),_T("打开文件"),(LPCTSTR)filename,0,0,0)){
_stprintf_s(filepath,_T("%s%s%s"),runpath,filename,MODE?_T(".dg"):_T(".udg"));//生成保存路径
//MessageBox(GetHWnd(),filepath,_T("aaa"),MB_OK|MB_ICONINFORMATION);
if(!_tfopen_s(&fp,filepath,_T("rb+"))){
fread(&g,sizeof(g),1,fp);
fclose(fp);
DrawMGraph();
}
else{
MessageBox(GetHWnd(),_T("文件不存在！！"),_T("错误"),MB_OK|MB_ICONWARNING);
}
}
break;
case 4: MessageBox(GetHWnd(),_T("ShortestPaths V1.0\nCode by LinXiang(PB16020923)"),_T("About"),MB_OK|MB_ICONINFORMATION);
break;
}
}
int IsInRange(int a,int up,int down){
return a<=up && a>=down;
}
int GetPosInVex(int x,int y){//获取当前坐标下的顶下标，没有返回-1
int i,xu=x+VEXRADIUS,xd=x-VEXRADIUS,yu=y+VEXRADIUS,yd=y-VEXRADIUS;
//反过来判断某个顶在不在x,y范围内，这样节省计算，不用算每个顶边界
for(i=0;i<g.vexnum;i++){
if(IsInRange(g.vexs[i].x,xu,xd) && IsInRange(g.vexs[i].y,yu,yd)) return i;
}
return -1;
}
void SetVexSelected(int i){
g.vexs[i].state=1;
DrawVex(i);//更新为选中状态
vsel=i;//记下当前选中顶
}
void SetVexNoSelected(){
g.vexs[vsel].state=0;
DrawVex(vsel);//更新为正常选中状态
vsel=-1;//
}
void GetRunPath(TCHAR *text,TCHAR *path){//获取当前运行路径
int pos;//最后一个\的位置
int i=0;
while(*(text+i)){
if(*(text+i)=='\\') pos=i;
i++;
}
_tcscpy_s(path,256,text);
path[pos+1]=0;
}
int _tmain(int argc,TCHAR *argv[])
{
GetRunPath(argv[0],runpath);
if(IDYES==MessageBox(GetHWnd(),_T("选择‘是’为进入 有向图 模式，\n选择‘否’为进入 无向图 模式。"),_T("选择模式"),MB_YESNO|MB_ICONQUESTION))
MODE=1;
else MODE=0;
InitUI();
CreateGraph(&g);
while(true){
MOUSEMSG m = GetMouseMsg();// 获取一条鼠标消息
switch(m.uMsg){
int vi;
case WM_MOUSEMOVE://移动
if(vmov!=-1){
g.vexs[vmov].x=m.x;
g.vexs[vmov].y=m.y;
DrawMGraph();//重绘全部
}
break;
case WM_RBUTTONDOWN://右键按下，开始移动
vi=GetPosInVex(m.x,m.y);
if(vi!=-1)
vmov=vi;
break;
case WM_RBUTTONUP://右键弹起，结束移动
if(vmov!=-1)
vmov=-1;
break;
case WM_LBUTTONDOWN://按下左键
if(m.mkCtrl){//同时按下CTRL
vi=GetPosInVex(m.x,m.y);
if(vi!=-1 && vsel!=-1 && vi!=vsel){//按下ctrl选择了一顶，并且之前已经选中一顶，而且两顶不同，则添新边
TCHAR tn[10]=_T("1");
if(InputBox(tn,128,_T("Input a arc weight"),_T("Add a arc"),(LPCTSTR)tn,0,0,0)){//输入了权
if(!MODE){//无向图
g.arcs[vi][vsel].w=g.arcs[vsel][vi].w=_ttoi(tn);
DrawArc(vsel,vi,MODE,0);
}
else{//有向图
g.arcs[vsel][vi].w=_ttoi(tn);
DrawArc(vsel,vi,MODE,0);
}
}
}
}
else if(m.mkShift){//同时按下SHIFT
vi=GetPosInVex(m.x,m.y);
if(vi!=-1 && vsel!=-1 && vi!=vsel){//按下ctrl选择了一顶，并且之前已经选中一顶，而且两顶不同，则求最短路径
DrawMGraph();//重绘全部,避免图中有画过其他路径
DijRes r=Dijkstra(g,vsel);//求出vel到各顶最短路径
int tmp=vi;//倒推路径，先画边
while(r.prev[tmp]!=-1){
DrawArc(r.prev[tmp],tmp,MODE,1);
tmp=r.prev[tmp];
}
tmp=vi;//倒推路径，再画顶
while(tmp!=-1){
DrawVex(tmp);
tmp=r.prev[tmp];
}
}
}
else{//仅仅按下左键
if(m.x<CONTROLWIDTH){//控制区
if(m.y%(SPACE+BUTTONHEIGHT)>SPACE)
OnButtonClick(m.y/(SPACE+BUTTONHEIGHT)+1);
}
else{//绘图区
int vi=GetPosInVex(m.x,m.y);
if(vi!=-1){//按下了某个顶
if(vsel!=-1) //如果有选中的，先取消选中状态
SetVexNoSelected();
SetVexSelected(vi);
}
else{//按下了空白区域
if(vsel!=-1){//如果有选中的，取消选中状态
SetVexNoSelected();
break;
}
//以下添加新顶
//TCHAR根据是否有UNICODE宏分别对应char和wchar_t
//tn相当于TCHAR* 也就是LPTSTR
TCHAR tn[MAX_NAME]=_T("0");
tn[0]+=g.vexnum;
if(InputBox(tn,128,_T("Input a name:"),_T("Add a vex"),(LPCTSTR)tn,0,0,0)){
//_T将字符串常量转为unicode版本，(LPCTSTR)把字符串变量转为常量
InsertVex(&g,tn,m.x,m.y);
DrawVex(g.vexnum-1);
}
}
}
}
break;
}
}
closegraph();// 关闭绘图窗口
return 0;
}