用Dijkstra算法的基本思路并且是用C语言编写出求最小路径的代码
1个回答
2013-11-06
展开全部
Dijkstra算法的基本思路是:假设每个点都有一对标号 (dj, pj),其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路),其长度等于零);pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下:
1) 初始化。起源点设置为:① ds=0, ps为空;② 所有其他点: di=∞, pi=?;③ 标记起源点s,记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离,并设置:
dj=min[dj, dk+lkj]
式中,lkj是从点k到j的直接连接距离。
3) 选取下一个点。从所有未标记的结点中,选取dj 中最小的一个i:
di=min[dj, 所有未标记的点j]
点i就被选为最短路径中的一点,并设为已标记的。
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*,作为前一点,设置:
i=j*
5) 标记点i。如果所有点已标记,则算法完全推出,否则,记k=i,转到2) 再继续。
#include <stdio.h>
#define true 1
#define false 0
#define I 9999 /* 无穷大 */
#define N 20 /* 城市顶点的数目 */
int cost[N][N] = {
{0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},
{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},
{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},
{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},
{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},
{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},
{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},
{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},
{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},
{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},
{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},
{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}
};
int dist[N]; /* 存储当前最短路径长度 */
int v0 = 'A' - 65; /* 初始点是 A */
void main()
{
int final[N], i, v, w, min;
/* 初始化最短路径长度数据,所有数据都不是最终数据 */
for (v = 0; v < N; v++) {
final[v] = false;
dist[v] = cost[v0][v];
}
/* 首先选v0到v0的距离一定最短,最终数据 */
final[v0] = true;
/* 寻找另外 N-1 个结点 */
for (i = 0; i < N-1; i++) {
min = I; /* 初始最短长度无穷大 */
/* 寻找最短的边 */
for (w = 0; w < N; w++) {
if (!final[w] && dist[w] < min) {
min = dist[w];
v = w;
}
}
final[v] = true; /* 加入新边 */
for (w = 0; w < N; w++) { /* 更新 dist[] 数据 */
if (!final[w] && dist[v] + cost[v][w] < dist[w]) {
dist[w] = dist[v] + cost[v][w];
}
}
}
for (i = 0; i < N; i++) { /* 显示到监视器 */
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}
}
1) 初始化。起源点设置为:① ds=0, ps为空;② 所有其他点: di=∞, pi=?;③ 标记起源点s,记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离,并设置:
dj=min[dj, dk+lkj]
式中,lkj是从点k到j的直接连接距离。
3) 选取下一个点。从所有未标记的结点中,选取dj 中最小的一个i:
di=min[dj, 所有未标记的点j]
点i就被选为最短路径中的一点,并设为已标记的。
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*,作为前一点,设置:
i=j*
5) 标记点i。如果所有点已标记,则算法完全推出,否则,记k=i,转到2) 再继续。
#include <stdio.h>
#define true 1
#define false 0
#define I 9999 /* 无穷大 */
#define N 20 /* 城市顶点的数目 */
int cost[N][N] = {
{0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},
{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},
{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},
{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},
{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},
{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},
{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},
{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},
{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},
{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},
{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},
{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}
};
int dist[N]; /* 存储当前最短路径长度 */
int v0 = 'A' - 65; /* 初始点是 A */
void main()
{
int final[N], i, v, w, min;
/* 初始化最短路径长度数据,所有数据都不是最终数据 */
for (v = 0; v < N; v++) {
final[v] = false;
dist[v] = cost[v0][v];
}
/* 首先选v0到v0的距离一定最短,最终数据 */
final[v0] = true;
/* 寻找另外 N-1 个结点 */
for (i = 0; i < N-1; i++) {
min = I; /* 初始最短长度无穷大 */
/* 寻找最短的边 */
for (w = 0; w < N; w++) {
if (!final[w] && dist[w] < min) {
min = dist[w];
v = w;
}
}
final[v] = true; /* 加入新边 */
for (w = 0; w < N; w++) { /* 更新 dist[] 数据 */
if (!final[w] && dist[v] + cost[v][w] < dist[w]) {
dist[w] = dist[v] + cost[v][w];
}
}
}
for (i = 0; i < N; i++) { /* 显示到监视器 */
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}
}
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询