floyd算法、Dijkstra算法实例讲解

最短路径之Dijkstra算法详细讲解
１最短路径算法
在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：
A→C→B=5(比上面第一步的A→B=6要短)
此时到D权值更改为A→C→B=5，
A→C→D=6，
A→C→E=7，
A→C→其它U中的顶点=∞，发现A→C→B=5权值为最短
3
选入B，此时S=<A、C、B>
此时最短路径A→A=0，A→C=3，A→C→B=5
以B为中间点
从A→C→B=5这条最短路径开始找
U=<D、E、F>
问题主要出在输出打印方面
Voidfind(int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraph G,int a,int b){
int k;
for(k = 0; k < G.vexnum; k++)
if(P[a][b][k]==TRUE && k!=a && k!=b){
（４）全局最短路径问题：求图中所有的最短路径。
用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。
本文主要研究Dijkstra算法的单源算法。
（１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。
（２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
（３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。
MGraph G;
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM],P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int v,w,k,a,b,i;
printf("请输入顶点数和弧数");
scanf("%d %d",&G.vexnum,&G.arcnum);
２Dijkstra算法
2.1 Dijkstra算法
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
find(P,G,a,k);
printf("\t%c",65+k);
find(P,G,k,b);
}
}
采用递归的思想一次寻找是否存在中间点然后打印出来。
问题出在红色部分，判定是否采用递归，未考虑k是否与a b相同，结果导致无限递归。从而发现stack overflow的错误提示有可能出于递归无法跳出，导致栈的溢出问题。
A→C→B→D=10(比上面第二步的A→C→D=6要长)
此时到D权值更改为A→C→D=6，
A→C→B→其它U中的顶点=∞，发现A→C→D=6权值为最短
4
选入D，此时S=<A、C、B、D>
此时最短路径A→A=0，A→C=3，A→C→B=5，A→C→D=6
以D为中间点，
从A→C→D=6这条最短路径开始找
int k;
for(k = 0; k < G.vexnum; k++)
if(P[a][b][k]==TRUE && k!=a && k!=b){
find(P,G,a,k);
printf("%c\t",65+k);
find(P,G,k,b);
}
}
测试结果
输入
（1000为无穷！~
输出
心得体会~。！！
懂得了floyd算法的思想，用邻接矩阵存储带权值的图。
// D[v][w]从v到w的最短路径的长度
for (v = 0; v < G.vexnum; v++)
for (w = 0; w < G.vexnum; w++){
D[v][w] = G.arcs[v][w];
for (k = 0; k < G.vexnum; k++)
P[v][w][k] = FALSE;
2.3 Dijkstra算法具体步骤
（1）初始时，S只包含源点，即S＝，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。
（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中。
2.4 Dijkstra算法举例说明
如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）
图一：Dijkstra无向图
算法执行步骤如下表：【注：图片要是看不到请到“相册--日志相册”中，名为“Dijkstra算法过程”的图就是了】
U=<F>
A→C→E→F=12(比上面第四步的A→C→D→F=9要长)此时到F权值更改为A→C→D→F=9
发现A→C→D→F=9权值为最短
6
选入F，此时S=<A、C、B、D、E、F>
此时最短路径A→A=0，A→C=3，
A→C→B=5，
A→C→D=6，
A→C→E=7，A→C→D→F=9
U集合已空，查找完毕。
G.kind=DG;
printf("请输入邻接矩阵\n");
for (v = 0; v < G.vexnum; v++)
foFra Baidu bibliotek (w = 0; w < G.vexnum; w++)
scanf("%d",&G.arcs[v][w]); //读入邻接矩阵
// P[v][w][k]为TRUE，则从v到w的最短路径中含有k节点
if (D[v][w] < INFINITY)
P[v][w][v] = P[v][w][w] = TRUE;
}
for (k = 0; k < G.vexnum; k++)
for (v = 0; v < G.vexnum; v++)
for (w = 0; w < G.vexnum; w++)
if (D[v][k] + D[k][w] < D[v][w]){
步骤
S集合中
U集合中
1
选入A，此时S=<A>
此时最短路径A→A=0
以A为中间点，从A开始找
U=<B、C、D、E、F>
A→B=6，A→C=3，
A→其它U中的顶点=∞，
发现A→C=3权值为最短
2
选入C，此时S=<A、C>
此时最短路径A→A=0，A→C=3以C为中间点，
从A→C=3这条最短路径开始找
U=<B、D、E、F>
U=<E、F>
A→C→D→E=8(比上面第二步的A→C→E=7要长)此时到E权值更改为A→C→E=7，A→C→D→F=9
发现A→C→E=7权值为最短
5
选入E，此时S=<A、C、B、D、E>
此时最短路径A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，以E为中间点，
从A→C→E=7这条最短路径开始找
printf("%c到%c最短路径为",65+a,65+b);
printf("%c\t",65+a);
find(P,G,a,b);
printf("%c\t",65+b);
printf("长度为%d",D[a][b]);
printf("\n");
}
}
void find(int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraph G,int a,int b){
2.2 Dijkstra算法思想
Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
D[v][w] = D[v][k] + D[k][w];
for (i = 0; i < G.vexnum; i++)
P[v][w][i] = P[v][k][i] || P[k][w][i];
}
for(a=0; a<G.vexnum; a++)
for(b=0; b<G.vexnum; b++)
if(D[a][b] < INFINITY && a!=b){
Floyd算法
实现Floyd算法，并求所示有向图中各顶点之间的最短路径及其长度。
算法思想
采用图的邻接矩阵存储，实现Floyd算法~，数组P[][][]存储是否存在中间点使长度缩短。
设计描述
数据存储结构类型的定义：
typedef struct MGraph{
char vexs[MAX_VERTEX_NUM];
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
GraphKind kind;
}MGraph;
源程序
#include<stdlib.h>
#include<stdio.h>
#define INFINITY 1000 //最大值
#define MAX_VERTEX_NUM 20 //最大顶点个数
intvexnum,arcnum; //图的当前顶点数和弧数
GraphKindkind; //图的种类标志
}MGraph;
void find(int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraph G,int a,int b);
void main(){
#define TRUE 1
#define FALSE 0
typedef enum{DG, DN, UDG, UDN}
GraphKind; //四种图类型
typedef struct MGraph{
charvexs[MAX_VERTEX_NUM]; //顶点向量
intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵