#include <iostream>
#include <stdio.h>
using namespace std;
#define MAXVEX 100
#define INF 6000
//定义比较的数字 表示无穷大 只要比你图中的权值运算涉及的值要大就可以了
/************************************************************************/
/* Dijkstra 算法思想
/* 1: 基本思想就是贪心法（核心思想） --->在写代码时候再说
/* 2: 这里就是找出源点到各个点最短距离 然后用这个最短距离+源点到另外一个点距离 如果< 就修改值这样不断修改就得出了
/************************************************************************/
void Dijkstra(int graph[][MAXVEX],int startVex,int VexNum)
{
int path[MAXVEX] = {-1}; //保存最终点最短路径的前一个点
int dist[MAXVEX] = {0};
int s[MAXVEX] = {0}; //标志是否在s的集合中--> 这里要涉及到Dijkstra 算法思想
int i,j,min = INF;
s[startVex] = 1; //把startvex 选到s集合中去 -->这里为下面选择最小值服务了 放在这里代码思路清晰点
for( i = 0; i < VexNum; i++)
{
dist[i] = graph[startVex][i] ; //这里就是开始贪心了 认为 startVex ---> 各个定点距离现在就是最短了。
if(dist[i] < INF)
{
path[i] = startVex; //保存到i 最短路径的前一个定点
}
else
{
path[i] = -1;
}
}
for(j = 0; j < VexNum; j++)
{
int min = INF;
int uVex = -1; //保存从没有选过的点中距离最短的点
for( i = 0; i < VexNum; i++)
{
if(s[i] == 0) //过滤条件--->把选择的点过滤掉
{
if( min > dist[i])
{
min = dist[i];
uVex = i;
}
}
}
//这样就得到一个顶点了
if(uVex != -1)//为什么要判断 因为 你可能没有最小的选择 但还在循环中的处理
{
s[uVex] = 1; //加入s集合 不加就会出现重复选择一个点 --->显然这样结果肯定是不对的
for(i = 0; i < VexNum; i++) //这里就是在修改dist 最短距离的值了 有可能几个点 比你直接2个点要短
{//我们只要dist[i]+dist[j] < dist[j] 距离就可以了
if(s[i] == 0)///dist[i] 是dist 最短的 这里就体现了贪心法了。
{
if(dist[i] > dist[uVex] + graph[uVex][i])
{
path[i] = uVex; //保存到达i 点 最短距离的前一个点
dist[i] = dist[uVex] + graph[uVex][i];
}
}
}
}
}
cout<<"打印Dijkstra"<<endl;
/////////////////////////
int stack[MAXVEX] = {0};
int top = -1;
//一个简单栈
/////////////////////////
for(i = 0; i < VexNum; i++)
{
int pre = path[i]; //获得到达i点最短路径的前一个定点
if(pre != -1)
{
cout<<"dist: "<<dist[i]<<endl;
while(pre != startVex) //
{
stack[++top] = pre; //进栈
pre = path[pre];
}
cout<<startVex<<"---->"<<i<<"路径: ";
cout<<startVex<<" ";
while(top!=-1)
{
cout<<stack[top--]<<" ";
}
cout<<i<<endl;
}
else
{
cout<<startVex<<"--->"<<i<<"没有路径"<<endl;
}
}
}
int main()
{
int cost[6][MAXVEX] ={
{0,50,10,INF,INF,INF},
{INF,0,15,50,10,INF},
{20,INF,0,15,INF,INF},
{INF,20,INF,0,35,INF},
{INF,INF,INF,30,0,INF},
{INF,INF,INF,3,INF,0}};
Dijkstra(cost,1,6);
return 1;
}
如上图：
假设1为起始点
我们会这样想比喻1 ->0 ： 我们会比较 1->0 这2点直接相同不如果不相同我们肯定找别的通往0（也肯定要以1为起始点的撒）点 ---》所以1->2->0 这样就得到了。
其实这就是最短路径的思路了 反正我学习的2个算法 Dijkstra 和Floyed 算法都是差不多这个思路。
我们贪心法恰好就是这个思路 我们找到起始点 这里是1 到各个点这里是0 , 2,3 路径距离 然后修改到各个点的值 （dist[i]--我们认为dist 放都是最短距离）。。这样就会得到我们想要结果了
如我们这个例子：1—》0 : 我们会开始的时候初始化 1->0 直接是为INF 无穷大 不通撒
1--3 是不是1 到各个点最短的不 不是 我们再找知道最短 的 这里是1 到2是最短的
这里我们就修改1->0值是dist[0] =60+102;1->3 值dist[3] =60+300;形成新dist。。
然后以继续上面重复。。。。。。。。。
所以1 –》2-》0
这里我画图只画了这几个 所以 不能很好说明
————————————————————————————————
弗洛伊德 思路起始也是差不多 只是边边 上面是点到点
//递归打印
void printPath(int start,int end,int path[][MAXVEX])
{
if(end != -1)
{
end = path[start][end];
printPath(start,end,path);
if(end!=-1)
cout<<end<<" ";
}
}
void Floyed(int cost[][MAXVEX],int n)
{
int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
int i,j,k,pre;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{
A[i][j] = cost[i][j];
path[i][j] = -1;
}
for( k = 0; k < n; k++)
{
for( i = 0; i < n; i++)
for( j = 0; j < n; j++)
if(A[i][j] > (A[i][k] + A[k][j]))
{
A[i][j] = A[i][k] + A[k][j];
path[i][j] = k;
}
}
printf("\n Floyed算法求解:\n");
for( i = 0; i < n; i++)
for(j = 0; j < n; j++)
if(i!=j)
{
printf(" %d->%d:",i,j);
if( A[i][j] == INF)
{
if(i!=j)
printf("不存在路径\n");
}
else
{
printf("路径长度为:%3d",A[i][j]);
printf("路径为%d ",i);
pre = path[i][j];
//////////////////
int stack[MAXVEX] = {0};
int top = -1;
//这里简单的栈 书上代码是错误的 打印是不对的 那本书的作者肯定是搞混了
////////////////
/*while(pre != -1)
{
//printf("%d ",pre);
stack[++top] = pre;
pre = path[i][pre];
}
while(top!=-1)
{
printf("%d ",stack[top--]);
}*/
printPath(i,j,path); //这里用的递归打印路径
printf(" %d\n",j);
}
}
}
int main()
{
int cost[6][MAXVEX] ={
{0,50,10,INF,INF,INF},
{INF,0,15,50,10,INF},
{20,INF,0,15,INF,INF},
{INF,20,INF,0,35,INF},
{INF,INF,INF,30,0,INF},
{INF,INF,INF,3,INF,0}};
//Dijkstra(cost,6,1);
Floyed(cost,6);
return 1;
}
posted on 2012-05-23 22:38
小鱼儿 阅读(251)
评论(0) 编辑 收藏 引用