社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
Dijkstra算法
1959年由Dijkstra提出,算法采用标号法,有两种标号,T 标号和P标号。T标号称为试探性标号(tentative label),P标号 为永久性标号(permanent label),给节点vi一个P标号表示从起 点vs到vi的最短路径的长度;给节点vi一个T标号表示从起点vs到 vi的估计的最短路径长度的上界;算法的每一步都会把某点的T 标号改为P标号,当终点vt得到P标号时,计算结束 。
算法步骤
图示如下:
寻找顶点V1至顶点V8的最短路径
使用C语言实现Dijkstra算法
使用一个存放各顶点的当前距离的数组dist,一旦从源点v到顶点k的最短路径已经求出,则disk[k]就是从源点到顶点k的最短路径长度。使用数组pre,pre[j]存放从源点到顶点j的最短路径中j前面的顶点。我们可以方便地从pre数组中求得从源点v到其他顶点的路径。
代码如下:
#include <stdio.h>
#include <stdlib.h>
#define maxv 20
typedef char VertexType;
typedef struct MGraph
{
VertexType vexes[maxv];//顶点表
int edges [maxv][maxv];//邻接矩阵,其元素值表示代价
int n,e;//顶点数、边数
}mgraph;
void Dijkstra(mgraph *g,VertexType v,int dist[maxv],int pre[maxv])
{
/*参数说明:g:邻接矩阵结构的图,v :源点,dist : 存放源点到各顶点距离,pre:存放路径*/
int vinx,i,j,k,min;
for(i=0; i <g->n; i++)
{
if(v == g->vexes[i])
{
vinx = i;
break;
}
}
for(i=0; i <g->n; i++)
{
dist[i] = g->edges[vinx][i];
visited[i] =0;
if(dist[i] < maxweight)
pre[i] = vinx;
else
pre[i] = -1;
}
visited[vinx] = 1;
pre[vinx] = 0;
for(i = 0; i < g->n; i++)
{
min = maxweight;
k = 0;
for(j = 0; j < g->n; j++)
{
if(visited[j] == 0)
if(dist[j] !=0 && dist[j] < min)
{
min = dist[j];
k = j;
}
}
if(k == 0)
continue;
visited[k] = 1;
for(j =0; j <g->n; j++)
{
if(visited[j] == 0 && g->edges[k][j] < maxweight)
{
if(dist[k] + g->edges[k][j] < dist[j])
{
dist[j] = dist[k] + g->edges[k][j];
pre[j] = k;
}
}
}
}
}
/*输出Dijkstra路径*/
void print_dpath(mgraph *g,int path[maxv],int v, int u)
{
/*查找从v 到 u的路径*/
int k;
k = path[u];
if(k == -1)
{
printf("no path!");
return;
}
printf("%c",g->vexes[u]);
while(k != v)
{
printf("<--");
printf("%c",g->vexes[k]);
k = path[k];
}
printf("<--%c",g->vexes[k]);
}
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!