最快通路算法
A. dijkstra的matlab程序看不懂，求解！
clear;
clc;
M=10000;%无穷远距离
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
a=a+a';%a66邻接矩阵，无向图
pb(1:length(a))=0;pb(1)=1;%存放p,t标号信息
index1=1;%存放标号顶点顺序
index2=ones(1,length(a));%存放始点到第i点最短通路中第i顶点前一顶点的序号
d(1:length(a))=M;d(1)=0;%存放由始点到第i点最短通路的值
temp=1;%算c1到其它点的最短路
while sum(pb)<length(a)
tb=find(pb==0);%找到标号为0的所有点
d(tb)=min(d(tb),d(temp)+a(temp,tb));%计算标号为0的点的最短路,其余已算过,再算结果还是一样
tmpb=find(d(tb)==min(d(tb)));%tmpb存储标号为0的点中最短路最短的点的tb值，即在find过程中的第几个
temp=tb(tmpb(1));%这个第几个在d中的真正位置
pb(temp)=1;%把这个点标号为1
index1=[index1,temp];%存放标号顶点顺序
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2%判断这个点前面是否有点
index=index(1);
end
index2(temp)=index;%记下这个点前面的点的标号
end
d, index1, index2
B. 图论的基本概念有哪些
图论基本概念
重要定义：
有向图：每条边都是有向边的图。
无向图：每条边都是无向边的图。
混合图：既有有向边又有无向边的图。
自回路：一条边的两端重合。
重数：两顶点间若有几条边，称这些边为平行边，两顶点a,b间平行边的条数成为（a,b）的重数。
多重图：含有平行边的图。
简单图：不含平行边和自回路的图。
注意！一条无向边可以用一对方向相反的有向边代替，因此一个无向图可以用这种方法转化为一个有向图。
定向图：如果对无向图G的每条无向边指定一个方向由此得到的有向图D。称为的G定向图.
底图：如果把一个有向图的每一条有向边的方向都去掉，得无向图G称为的D底图。
逆图：把一个有向图D的每条边都反向由此得到的图称为D的逆图。
赋权图：每条边都赋上了值。
出度：与顶点相连的边数称为该定点的度数，以该定点为始边的边数为出度。 入度：以该定点为终边的边数为入度。
特殊！度数为零的定点称为孤立点。度数为一的点为悬挂点。
无向完全图：在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。Kn
完全有向图：在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。
竟赛图：阶图中如果其底图是无向完全图，则程此有向完全图是竟塞图。
注意！n阶有向完全图的边数为n的平方；无向完全图的边数为n(n-1)/2。
下面介召图两种操作：①删边：删去图中的某一条边但仍保留边的端点。
②删点：删去图中某一点以及与这点相连的所有边。
子图：删去一条边或一点剩下的图。
生成子图：只删边不删点。
主子图：图中删去一点所得的子图称的主子图。
补图：设为阶间单无向图，在中添加一些边后，可使成为阶完全图；由这些添加边和的个顶点构成的图称为的补图。
重要定理：
定理5.1.1 设图G是具有n个顶点m条边的有向图，其中点集V={v,v,….,v}
deg+(vi)=deg-(vi)=m
定理5.1.2 设图G是具有n个顶点m条边的无向图，其中点集V={v,v,v,……,v}
deg(vi)=2m
推论 在无向图中，度数为积数的顶点个数为偶数。
通路和富权图的最短通路
1通路和回路
基本概念：
通路的长度：通路中边的条数。
回路：如果通路中始点与终点相同。
简单通路：如果通路中各边都不相同。
基本通路：如果通路中各顶点都不相同。显然（基本通路一定是简单通路，但简单通路不一定是基本通路）
可达：在图G中如果存在一条v到d通路则称从v到d是可达。
连通：在无向图中如果任意两点是可达的，否则是不连通的。
强连通：在有向图中如果任意两点是互可达的。
单向连通：在有向图中如果存在任意两点的通路。
弱连通：在有向图中如果其底图是连通的。
权：在图的点或边上表明某种信息的数。
赋权图：含有权的图。
赋权图的最短通路问题的算法：先求出到某一点的最短通路，然后利用这个结果再去确定到另一点的最短通路，如此继续下去，直到找到到的最短通路为止。
指标：设V是图的点集，T是V的子集，且T含有z但不含a，则称T为目标集。在目标集T中任取一个点t，由a到t但不通过目标集T中其它点所有通路中，个边权和的最小者称为点t关与T的指标记作DT(t)。
图和矩阵
住意两个的区别：A·A 中元素的意义：当且仅当a 和a 都是1时，a a =1而a 和a 都为1意味着图G中有边(v ,v )和(v ,v )。于是可得如下结论：从顶点v 和v 引出的边，如果共同终止于一些顶点，则这些终止顶点的数目就是b 的值；特别对于b ，其值就是v 的出度。
A ·A中元素的意义：当且仅当a 和a 都为1时，a a =1，这意味着图中有边(v ,v )和(v ,v )。于是的得如下结论：从某些点引出的边，如果同时终止于v 和v ，则这样的顶点数就是的值。特别对于b ，其值就是的v 入度。
幂A 中元素的意义：当m=1时，a 中的元素=1，说明存在一条边(v ,v )，或者说从v 到v 存在一条长度为一的通路。
A 中元素a 表示从v 到v 的长度为m的所有通路的数目。
欧拉图
主要定义：
如果图中存在一条通过图中个边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图称为欧拉图。
如果图中存在一条通过图中各边一次且仅一次的通路，则称此回路为欧拉通路，具有欧拉通路的图称为半欧拉图。
主要定理：一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数。
一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点。
设图G是有向连通图，图G是欧拉图的充要条件是图中每个顶点的入度和出度相等。
设图G是有向连通图，图G是半欧拉图的充要条件是至多有两个顶点，其中一个顶点入度比它的出度大1，另一个顶点入度比它的出度少1；而其他顶点的入度和出度相等。
哈密顿图
主要定义：如果图G中存在一条通过图G中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。
如果图G中存在一条通过图G中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。
主要定理：设图G是哈密顿图，如果从G中删去个p顶点得到图G’，则图G’的连通分支数小于等于p。
设图G是具有n个顶点的无向简单图，如果G中任意两个不同顶点的度数之和大于等于n-1，则具有哈密顿通路，即G是半哈密顿图。
设图G是具有n个顶点的无向简单图，如果G中任意两个不同顶点的度数之和大于等于n，则G具有哈密顿回路，即G是哈密顿图。
C. 网络流理论的常用算法
1、augment path，直译为“增广路”，其思想大致如下：
原有网络为G，设有一辅助图G'，其定义为V(G') = V(G)，E(G')初始值（也就是容量）与E(G)相同。每次操作时从Source点搜索出一条到Sink点的路径，然后将该路径上所有的容量减去该路径上容量的最小值，然后对路径上每一条边<u,v>添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此时辅助图上的正向流就是最大流。
我们很容易觉得这个算法会陷入死循环，但事实上不是这样的。我们只需要注意到每次网络中由Source到Sink的流都增加了，若容量都是整数，则这个算法必然会结束。
寻找通路的时候可以用DFS，BFS最短路等算法。就这两者来说,BFS要比DFS快得多，但是编码量也会相应上一个数量级。
增广路方法可以解决最大流问题，然而它有一个不可避免的缺陷，就是在极端情况下每次只能将流扩大1（假设容量、流为整数），这样会造成性能上的很大问题，解决这个问题有一个复杂得多的算法，就是预推进算法。
2、push label，直译为“预推进”算法。
[等待完善]
D. 链路状态路由算法的算法工作原理
链路状态选路算法的工作原理如下
（1）在参与链路状态选路的路由器集合中，每个路由器都需要通过某种机制来了解自己所连接的链路及其状态。
（2）各路由器都能够将其所连接的链路的状态信息通知给网络中的所有其他路由器，这些链路信息包括链路状态、费用以及链路两端的路由器等。
（3）链路状态信息的通过链路状态分组（LSP）来向整个网络发布。一个LSP通常包含源路由器的标识符、相邻路由器的标识符，以及而知之间链路的费用。每一个LSP都将被网络中的所有的路由器接收，并用于建立网络整体的统一拓扑数据库。由于网络中所有的路由器都发送LSP，经过一段时间以后，每一个路由器都保持了一张完整的网络拓扑图，再在这个拓扑图上，利用最短通路算法（例如Dijkstra算法等），路由器就可以计算出从任何源点到任何目的地的最佳通路。
这样，每一个路由器都能够利用通路最短的原则建立一个以本路由器为根、分支到所有其他路由器的生成树，依据这个生成树就可以很容易地计算出本路由器的路由表。
E. 用递归算法找出迷宫中所有可行的路径
回溯啊、、、
int ans[1000][2],t=0； //ans数组里存的是每一步的解
void dfs(int x,int y)
{
if (x==x0&&y==y0) {print();return ;} //x0 y0是出口坐标 print（）是输出一个合法解的函数 这个很 简单你自己写吧
然后是枚举下一步可以到达的点 因为我不知道走的规则所以写不出来 只能先假设xx yy是x、y能到达的一个点吧 你可以用for循环枚举能到的点
for (xx.....)
for (yy....)
if (xx,yy满足条件）
{
t++;
ans[t][0]=xx;
ans[t][1]=yy;
dfs(xx,yy)
t--;
}
}
F. 求用C++Dijkastra算法解决最短通路问题
#include<string.h>
#defineN1010
#definenull0
longmap[N][N],v[N];
voiddijkstra(longn,longs,longt){
longq[N],i,j,k,flag=1;
memset(v,0x7f,sizeof(v));
memset(q,1,sizeof(q));
v[s]=0;
for(k=0;k<n;k++){
for(j=1;j<=n&&q[j]==0;j++);
if(j>n)break;
for(i=j+1;i<=n;i++)
if(q[i]&&v[i]<v[j])j=i;
q[j]=0;
for(i=1;i<=n;i++)
if(j!=i&&map[j][i]!=null&&v[j]+map[j][i]<v[i])
v[i]=v[j]+map[j][i];
}
}
来自北理工某大神模板
G. 最短路径
// dijsktra.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#define N 12
#include <iostream>
using namespace std;
const static int soure[N][N] =
{
/*
这填邻接矩阵
*/
};
int min(int arr[N],bool bj[])
{
int tmp = 999;
int temp = 0;
for(int i=0; i<N; i++)
{
if((arr[i]<tmp)&&(bj[i]==true))
{
tmp = arr[i];
temp = i;
}
}
return temp;
}
class dijsktra
{
private:
int dist[N][N];
int path[N][N];
int final[N][N];
bool flag[N];
public:
void Doing()
{
for(int i=0; i<N; i++)
{
int temp = 0;
for(int j=0; j<N; j++)
{
flag[j] = true;
}
for(int j=0; j<N; j++)
{
dist[i][j] = soure[i][j];
path[i][j] = i;
}
flag[i] = false;
temp = min(dist[i],flag);
flag[temp] = false;
for(int j=1; j<N; j++)
{
for(int k=0; k<N; k++)
{
if((flag[k] == true)&&((soure[temp][k]+dist[i][temp])<dist[i][k]))
{
dist[i][k] = soure[temp][k]+dist[i][temp];
path[i][k] = temp;
}
}
temp = min(dist[i],flag);
flag[temp] = false;
}
}
}
void print()
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<dist[i][j]<<","<<path[i][j]<<" ";
}
cout<<endl;
}
}
void l_print()
{
int i,j;
cout<<"请输入i,j的值:";
cin>>i>>j;
cout<<"最短路径长度为："<<dist[i][j]<<endl;
cout<<"路径为";
int temp = j;
while(path[i][temp]!=i)
{
cout<<temp<<"<-";
temp = path[i][temp];
}
cout<<temp<<"<-";
cout<<i<<endl;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
dijsktra test;
test.Doing();
test.print();
test.l_print();
system("pause");
return 0;
}
H. 最短路径算法应用在哪些方面
网络通路， 凡事可以使用图作为模型的问题都基本可以用到，比如游戏地图的寻找，交通路线的寻找，这种最短路径都可以用。
I. 离散数学是学什么的
第l章 基础：逻辑、集合和函数
1．1 逻辑
1．1．1 引言
1．1．2 命题
1．1．3 翻译语言的句子
1．1．4 布尔检索
l. 1．5 逻辑运算和位运算练习
1．2 命题等价
1. 2．1 引言
1．2．2 逻辑等价练习
1．3 谓词和量词
1．3．1 引言
1．3．2 量词
1．3．3 翻译语句为逻辑表达式
1．3．4 选自Lewis Carroll的例子(选读)
1．3．5 绑定变量
1．3．6 否定练习
1．4 集合
1．4．1 引言
1．4．2 幂集合
1．4．3 笛卡儿积练习
1．5 集合运算
1．5．1 引言
1．5．2 集合相等
1．5．3 扩展的并集和交集
1．5．4 集合的计算机表示练习
1．6 函数
1．6．1 引言
1．6．2 一对一函数和映上函数
1．6．3 反函数和函数组合
1．6．4 函数的图像
1．6．5 几个重要的函数练习
1．7 序列与求和
1．7．1 引言
1．7．2 序列
1．7．3 特殊的整数序列
1．7．4 求和
1．7．5 基数(选读)练习
1．8 函数增长
1．8．1 引言
1．8．2 大O符号
1．8．3 函数组合的增长
1．8．4 大Ω和大Ξ符号
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第2章 基础：算法、整数和矩阵
2．1 算法
2．1．1 引言
2．1．2 搜索算法练习
2．2 算法的复杂性
2．2．1 引言练习
2．3 整数和除法
2．3．1 引言
2．3．2 除法
2．3．3 素数
2．3．4 除法算法
2．3．5 最大公约数和最小公倍数
2．3．6 模运算
2. 3．7 同余应用
2．3．8 密码学练习
2．4 整数和算法
2．4．1 引言
2．4．2 欧几里德算法
2．4．3 整数表示
2．4．4 整数运算算法练习
2．5 数论应用
2．5．1 引言
2．5．2 若干有用的结果
2．5．3 线性同余
2．5．4 中国余数定理
2．5. 5 大整数的计算机算术运算
2．5．6 伪素数
2．5．7 公钥密码学
2．5．8 RSA加密
2．5．9 RSA解密
2．5．10 用RSA作公钥系统练习
2．6 矩阵
2．6．1 引言
2．6．2 矩阵运算
2．6．3 矩阵乘法运算
2．6．4 矩阵的转置和幂
2．6．5 0-1矩阵练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第3章 数学推理
3．1 证明方法
3．1．1 引言
3．1．2推理规则
3．1．3 谬误
3．1．4 带量词命题的推理规则
3．1．5 证明定理的方法
3．1．6 定理与量词
3．1．7 停机问题
3．1．8 关于证明的一些评注练习
3．2 数学归纳法
3．2．1 引言
3．2．2 良序性
3．2．3 数学归纳法
3．2．4 数学归纳法证明的例子
3．2．5 数学归纳法的第二原理练习
3．3 递归定义
3．3．1 引言
3．3．2 递归地定义函数
3．3．3 递归地定义集合练习
3．4 递归算法
3．4．1 引言
3．4．2 递归与迭代练习
3．5 程序正确性
3．5．1 引言
3．5．2 程序验证
3．5．3 推理规则
3．5．4 条件语句
3．5．5 循环不变量
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第4章 计数
4．1 计数的基础
4．1．1 引言
4．1．2 基本的计数原则
4．1．3 容斥原理
4．1．4 树图练习
4．2 鸽巢原理
4．2．1 引言
4．2．2 推广的鸽巢原理
4．2．3 巧妙使用鸽巢原理练习
4．3 排列与组合
4．3．1 引言
4．3．2 排列
4．3．3 组合
4．3．4 二项式系数
4．3．5 二项式定理练习
4．4 离散概率
4．4．1 引言
4．4．2 有限概率
4．4．3 事件组合的概率
4．4．4 概率的推理练习
4．5 概率论
4．5．1 引言
4．5．2 概率赋值
4．5．3 事件的组合
4．5．4 条件概率
4．5．5 独立性
4．5．6 伯努利实验与二项式分布
4．5．7 随机变量
4．5．8 期望值
4．5．9 独立随机变量
4．5．10 方差
4．5．11 切比雪夫不等式
4．5．12 平均状态下的计算复杂性练习
4．6 一般性的排列和组合
4．6．1 引言
4．6．2 有重复的排列
4．6．3 有重复的组合
4．6．4 具有不可区别物体的集合的排列
4．6．5 把物体放入盒子练习
4. 7 生成排列和组合
4．7．1 引言
4．7．2 生成排列
4．7．3 生成组合
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第5章 高级计数技术
5．1 递推关系
5．1．1 引言
5．1．2 递推关系
5．1．3 用递推关系构造模型练习
5．2求解递推关系
5．2．1 引言
5．2．2 求解常系数线性齐次递推关系
5．2．3 常系数线性非齐次的递推关系练习
5．3分而治之关系
5．3．1 引言
5．3．2 分而治之关系练习
5．4 生成函数
5．4．1 引言
5．4．2 关于幂级数的有用的事实
5．4．3 计数问题与生成函数
5．4．4 使用生成函数求解递推关系
5．4．5 使用生成函数证明恒等式练习
5．5 容斥
5．5．1 引言
5．5．2 容斥原理练习
5．6 容斥原理的应用
5．6．1 引言
5．6．2 容斥原理的另一种形式
5．6．3伊拉脱森筛
5．6．4 映上函数的个数
5．6．5 错位排列
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第6章 关系
6．1 关系及其性质
6．1．1 引言
6．1．2 函数作为关系
6．1．3 集合上的关系
6．1．4 关系的性质
6．1．5 关系的组合练习
6．2 n元关系及其应用
6．2．1 引言
6. 2．2 n元关系
6．2．3 数据库和关系练习
6．3 关系的表示
6．3．1 引言
6．3．2 用矩阵表示关系
6．3．3 用图表示关系练习
6．4 关系的闭包
6．4．1 引言
6．4．2 闭包
6．4．3 有向图的路径
6．4．4 传递闭包
6．4．5 沃舍尔算法练习
6．5 等价关系
6．5．1 引言
6．5．2 等价关系
6．5．3 等价类
6．5．4 等价类与划分练习
6．6 偏序
6．6．1 引言
6．6．2 字典顺序
6．6．3 哈斯图
6. 6．4 极大元素与极小元素
6．6．5 格
6．6．6 拓扑排序
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第7章 图
7．1 图的介绍
7．1．1 图的种类
7．1．2 图模型练习
7．2 图的术语
7．2．1 引言
7．2．2 基本术语
7．2．3 一些特殊的简单图
7．2．4 偶图
7．2．5 特殊类型的图的一些应用
7．2．6 从旧图到新图练习
7．3 图的表示和图的同构
7．3．1 引言
7．3．2 图的表示
7．3．3 相邻矩阵
7．3．4 关联矩阵
7．3．5 图的同构练习
7. 4 连通性
7．4．1 引言
7．4．2 通路
7．4．3 无向图连通性
7．4．4 有向图中的连通性
7．4．5 通路与同构
7．4．6 统计顶点之间的通路练习
7．5 欧拉通路与哈密顿通路
7．5．1 引言
7．5．2 欧拉回路和欧拉通路的充要条件
7．5．3 哈密顿通路和回路练习
7．6 最短通路问题
7．6．1 引言
7．6．2 一个最短通路算法
7．6．3 旅行推销员问题练习
7．7 平面性图
7．7．1 引言
7．7．2 欧拉公式
7．7．3 库拉图斯基定理练习
7．8 图着色
7．8．1 引言
7．8．2 图着色的应用
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第8章 树
8．1 介绍树
8．1．1 树作为模型
8．1．2 树的性质练习
8．2 树的应用
8．2．1 引言
8．2．2 二叉搜索树
8．2．3 决策树
8．2．4 前缀码练习
8．3 树的遍历
8．3．1 引言
8．3．2 通用地址系统
8．3．3 遍历算法
8．3．4 中缀、前缀和后缀记法练习
8．4 树与排序
8．4．1 引言
8．4．2 排序的复杂性
8．4．3 冒泡排序
8．4．4 归并排序练习
8．5 生成树
8．5．1 引言
8．5．2 一些构造生成树的算法
8．5．3 回溯练习
8．6 最小生成树
8．6．1 引言
8．6．2 最小生成树算法
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第9章 布尔代数
9．1 布尔函数
9．1．1 引言
9．1．2 布尔表达式和布尔函数
9．1．3 布尔代数中的恒等式
9．1．4 对偶性
9．1．5 布尔代数的抽象定义练习
9．2 布尔函数的表示
9．2．1 积之和展开式
9．2．2 函数完备性练习
9．3 逻辑门电路
9．3．1 引言
9．3. 2 门的组合
9．3．3 电路的例子
9．3．4 加法器练习
9．4 电路的极小化
9．4．1 引言
9．4．2 卡诺图
9．4．3 无需在意条件
9．4．4 奎因-莫可拉斯基方法
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第10章 计算模型
10．1 语言和文法
10．1．1 引言
10．1．2 短语结构文法
10．1．3 短语结构文法的类型
10．1．4 派生树
10．1．5 巴科斯-诺尔范式练习
10．2 带输出的有限状态机
10．2．1 引言
10．2．2 带输出的有限状态机练习
10．3 不带输出的有限状态机
10．3．1 引言
10．3．2 串的集合
10．3．3 有限状态自动机练习
10．4 语言的识别
10．4．1 引言
10．4．2 正则集合
10．4．3 克莱因定理
10．4．4 正则集合和正则文法
10．4．5 一个不能由有限状态自动机识别语言
10．4．6 一些更强大的机器练习
10．5 图灵机
10．5．1 引言
10．5．2 图灵机的定义
10．5．3 用图灵机识别集合
10．5．4 用图灵机计算函数
10．5．5 不同类型的图灵机
10. 5．6 丘奇-图灵论题
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
附录A 指数函数和对数函数
附录B 伪代码
奇数练习题答案
推荐读物 如果想成为真正的程序员，学好离散数学是很重要的，但刚学时也有点难度。
J. 迷宫数组 最短路径算法 我， 我， 我给分60！
//对角线也可以走：如从1,3到2,4最短路径为根号2
//如果对角线不想，两个for循环条件判断稍微修改下：
//代码如下：
//输出-1 表示找不到路径
/*
给个数组，0表示通路，1表示阻碍，然后给任意两个0的坐标，可以找到它们之间的最短路径并打印出来
比如说数组是 1 0 0 0 1
1 1 1 0 1
1 1 0 0 1
1 0 0 0 1
1 0 1 1 1
然后我就可以找到第一行第二个数和第五行第二个数之间的最短路径了
*/
#include <stdlib.h>
#include <math.h>
#include <windows.h>
#include <stdio.h>
#define M 5
#define N 5
typedef struct coordinate{
short int x;
short int y;
} COORDINATE;
COORDINATE path[M*N];//全局变量，存储已访问结点
float getminpath(COORDINATE *,COORDINATE *,char [][N],COORDINATE *);
void main()
{
memset(path,0,sizeof(COORDINATE)*M*N);
char maze[M][N]={
'\1','\0','\0','\0','\1',
'\1','\1','\1','\0','\1',
'\1','\1','\0','\0','\1',
'\1','\0','\0','\0','\1',
'\1','\0','\1','\1','\1',
};
COORDINATE a,b;
float dis;
do{
system("cls");
printf("请输入起点坐标：\n如1,2为第一行第二个数\n");
printf("取值范围1～%d,1～%d\n",M,N);
scanf("%hd,%hd",&a.x,&a.y);
printf("请输入终点坐标：\n如5,2为第五行第二个数\n");
printf("取值范围1～%d,1～%d\n",M,N);
scanf("%hd,%hd",&b.x,&b.y);
a.x--;
a.y--;
b.x--;
b.y--;
dis=getminpath(&a,&b,maze,path);
printf("最短路径为：%f\n",dis);
system("pause");
} while(getchar()!=EOF);
}
float getminpath(COORDINATE *from,COORDINATE *to,char maze[][5],COORDINATE *visited)
//从from结点到to结点可以分成两步，1.从from到from的相邻结点。2.再到to结点，这就是一个递归的过程
//将已访问结点存放入visited中
{
COORDINATE *nearpt=(COORDINATE*)malloc(sizeof(COORDINATE)*1);
memset(nearpt,0,sizeof(COORDINATE));
int i,j;
float min=0;//存储最短路径的值
COORDINATE *pvisit;//遍历已访问结点的指针
char reflag;//相邻结点是否 “已访问” 的flag
float dis=-1;//距离
if(from==0||to==0||maze==0)
{
return -1;
}
else
{
if(from->x==to->x&&from->y==to->y)//坐标相同，表示已到达
{
dis=0;
}
else
{
for(i=-1;i<=1;i++)
{
for(j=-1;j<=1;j++)
{
if(i==0&&j==0)
{
continue;
}
nearpt->x=from->x+i;
nearpt->y=from->y+j;
if(nearpt->x<0||nearpt->x>M-1||nearpt->y<0||nearpt->y>N-1)//越界
{
continue;
}
if(maze[nearpt->x][nearpt->y]!='\0')//非零为障碍，继续下一次循环
{
continue;
}
reflag='\0';//初值为'\0'，表示未访问过
for(pvisit=path;pvisit<visited;pvisit++)//搜索已访问结点
{
if(pvisit->x==nearpt->x&&pvisit->y==nearpt->y)
{
reflag='\1';//该结点已经访问过了
break;
}
}
if(reflag=='\1')
{
continue;
}
else
{
visited->x=from->x;//将from结点加入已访问结点数组中
visited->y=from->y;
dis=getminpath(nearpt,to,maze,visited+1);//递归
if(dis>=0)
{
dis+=sqrt((nearpt->x-from->x)*(nearpt->x-from->x)+(nearpt->y-from->y)*(nearpt->y-from->y));
// printf("%d,%d到%d,%d\t距离：%3f\n",from->x,from->y,to->x,to->y,dis);
if(min==0)//第一次，还没将dis的值赋给m过
{
min=dis;
}
else
{
if(dis<min)
{
min=dis;
}
else
{
}
}
}
visited->x=0;//清除from结点
visited->y=0;
}
}
}
}
}
free(nearpt);
if(min>0)
{
return min;
}
else
{
return dis;
}
}