一、概念：
最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：
确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。
确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
全局最短路径问题 - 求图中所有的最短路径。
二、 最短路径--Dijkstra 算法
思路：先遍历一下还没有在最短路中的点，选出一个距离 已经在最短路集合中的点 距离最近的点，并把它加入到最短路中，并且更新所有点的最短路，直到所有的点都加入到最短路中。
代码如下
Dijkstra 算法
G: 网图;
v0: V0开始的顶点;
p[v]: 前驱顶点下标;
D[v]: 表示从V0到V的最短路径长度和;
*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
int v,w,k,min;
k = 0;
/*final[w] = 1 表示求得顶点V0~Vw的最短路径*/
int final[MAXVEX];
/*1.初始化数据*/
for(v=0; v<G.numVertexes; v++)
{
//全部顶点初始化为未知最短路径状态0
final[v] = 0;
//将与V0 点有连线的顶点最短路径值;
(*D)[v] = G.arc[v0][v];
//初始化路径数组p = 0;
(*P)[v] = 0;
}
//V0到V0的路径为0
(*D)[v0] = 0;
//V0到V0 是没有路径的.
final[v0] = 1;
//v0到V0是没有路径的
(*P)[v0] = -1;
//2. 开始主循环,每次求得V0到某个顶点的最短路径
for(v=1; v<G.numVertexes; v++)
{
//当前所知距离V0顶点最近的距离
min=INFINITYC;
/*3.寻找离V0最近的顶点*/
for(w=0; w<G.numVertexes; w++)
{
if(!final[w] && (*D)[w]<min)
{
k=w;
//w顶点距离V0顶点更近
min = (*D)[w];
}
}
//将目前找到最近的顶点置为1;
final[k] = 1;
/*4.把刚刚找到v0到v1最短路径的基础上,对于v1 与 其他顶点的边进行计算,得到v0与它们的当前最短距离;*/
for(w=0; w<G.numVertexes; w++)
{
//如果经过v顶点的路径比现在这条路径长度短,则更新
if(!final[w] && (min + G.arc[k][w]<(*D)[w]))
{
//找到更短路径, 则修改D[W],P[W]
//修改当前路径的长度
(*D)[w] = min + G.arc[k][w];
(*P)[w]=k;
}
}
}
}
三、最短路径--弗洛洛伊德(Floyd)算法
思路：可以将问题分解:
第一、先找出最短的距离
第二、然后在考虑如何找出对应的行进路线。
如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间经过k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)>d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。
基本步骤：
定义n×n的方阵序列D-1, D0 , … Dn－1,
初始化： D-1＝C
D-1[v][w]＝边<v,w>的长度，表示初始的从i到j的最短路径长度，即它是从v到w的中间不经过其他中间点的最短路径。
迭代：设Dk-1已求出，如何得到Dk（0≤k≤n-1）？
Dk-1[v][w]表示从i到j的中间点不大于k-1的最短路径p：v…w，
考虑将顶点k加入路径p得到顶点序列q：v…k…w，
若q不是路径，则当前的最短路径仍是上一步结果：Dk[v][w]= Dk－1[v][w]；
否则若q的长度小于p的长度，则用q取代p作为从i到j的最短路径
因为q的两条子路径v…k和k…w皆是中间点不大于k－1的最短路径，所以从v到w中间点不大于k的最短路径长度为：
Dk[v][w]＝min{ Dk-1[v][w], Dk-1[v][k] +Dk-1[k][w] }
代码如下：
#include <stdio.h>
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* 11.1 构成邻近矩阵 */
void CreateMGraph(MGraph *G)
{
int i, j;
/* printf("请输入边数和顶点数:"); */
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITYC;
}
}
G->arc[0][1]=1;
G->arc[0][2]=5;
G->arc[1][2]=3;
G->arc[1][3]=7;
G->arc[1][4]=5;
G->arc[2][4]=1;
G->arc[2][5]=7;
G->arc[3][4]=2;
G->arc[3][6]=3;
G->arc[4][5]=3;
G->arc[4][6]=6;
G->arc[4][7]=9;
G->arc[5][7]=5;
G->arc[6][7]=2;
G->arc[6][8]=7;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/*
Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。
Patharc 和 ShortPathTable 都是二维数组;
*/
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
int v,w,k;
/* 1. 初始化D与P 矩阵*/
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
/* D[v][w]值即为对应点间的权值 */
(*D)[v][w]=G.arc[v][w];
/* 初始化P P[v][w] = w*/
(*P)[v][w]=w;
}
}
//2.K表示经过的中转顶点
for(k=0; k<G.numVertexes; ++k)
{
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
/*如果经过下标为k顶点路径比原两点间路径更短 */
if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
{
/* 将当前两点间权值设为更小的一个 */
(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
/* 路径设置为经过下标为k的顶点 */
(*P)[v][w]=(*P)[v][k];
}
}
}
}
}
int main(void)
{
printf("Hello,最短路径弗洛伊德Floyd算法");
int v,w,k;
MGraph G;
Patharc P;
ShortPathTable D; /* 求某点到其余各点的最短路径 */
CreateMGraph(&G);
ShortestPath_Floyd(G,&P,&D);
//打印所有可能的顶点之间的最短路径以及路线值
printf("各顶点间最短路径如下:\n");
for(v=0; v<G.numVertexes; ++v)
{
for(w=v+1; w<G.numVertexes; w++)
{
printf("v%d-v%d weight: %d ",v,w,D[v][w]);
//获得第一个路径顶点下标
k=P[v][w];
//打印源点
printf(" path: %d",v);
//如果路径顶点下标不是终点
while(k!=w)
{
//打印路径顶点
printf(" -> %d",k);
//获得下一个路径顶点下标
k=P[k][w];
}
//打印终点
printf(" -> %d\n",w);
}
printf("\n");
}
//打印最终变换后的最短路径D数组
printf("最短路径D数组\n");
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
printf("%d\t",D[v][w]);
}
printf("\n");
}
//打印最终变换后的最短路径P数组
printf("最短路径P数组\n");
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
printf("%d ",P[v][w]);
}
printf("\n");
}
return 0;
}
网友评论