Question

求Dijkstra算法的C语言实现

有非负赋权图，少量节点（五六个），求从起点（A点）到终点的最短路径的算法，用C语言实现。我想首先用二维数组列出各点的距离矩阵，然后用Dijkstra算法进行迭代求解。网上多数C语言实现的算法不带二维数组的输入，求大神解答

Answer 1

//Dijkstra算法 C语言实现 2008-08-26 12:07 #include<stdio.h>
#include<stdlib.h> #define INFINITY 1000000000 //最大距离
#define MAX_NODES 1024 //最大节点数
int n,dist[MAX_NODES][MAX_NODES]; //dist[i][j]表示从 i 到 j 的距离 void shortest_path(int s, int t, int path[])
{
struct state
{
int predecessor; //前驱节点
int length; //到起始点的距离
enum {permanent, tentative} label;
}state[MAX_NODES];
int i,k,min;
struct state * p;
for(p=&state[0]; p<&state[n]; p++)
{
p->predecessor = -1;
p->length = INFINITY;
p->label = tentative;
}
state[t].length = 0;
state[t].label = permanent;

k = t; //k 是当前工作节点
do
{
for(i=0; i<n; i++)
{
if(dist[k][i]!=0 && state[i].label==tentative)
{
if(state[k].length+dist[k][i]<state[i].length)
{
state[i].length = state[k].length+dist[k][i];
state[i].predecessor = k;
}
}
}

k=0;
min=INFINITY;
for(i=0; i<n; i++)
{
if(state[i].label==tentative && state[i].length<min)
{
k=i;
min=state[i].length;
}
}
state[k].label = permanent;
}while(k!=s);

i=0;
k=s;
do
{
path[i++] = k;
k = state[k].predecessor;
}while(k>=0);
}