# 单源最短路径算法——Dijkstra算法

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define MAXN (10001)
#define INF  (1<<16)

typedef struct _Vertex
{
int w[MAXN];
int cw;
int know;
int dis;
int path;
int ew[MAXN]; /*The edge weight of curent vertex to w[i] */

}Graph;

Graph G[MAXN];

{
int i, k;
int n, m, ew;

scanf ("%d", &n );
for ( i = 0 ; i < n; i++ ) {
scanf ("%d", &m ); G[i].cw = m; G[i].know = 0; G[i].dis = INF; G[i].path = -1;
for ( k = 0; k < m; k++ ) scanf ("%d%d", &G[i].w[k], &G[i].ew[k] );
}

return n;
}

int find ( int n )
{
int i;
int m;

for ( m = -1, i = 0; i < n; i++ ) if ( !G[i].know ) { m = i; break; }
if ( m < 0 ) return -1;

for ( i = m + 1; i < n; i++ ) {
if ( !G[i].know ) {
if ( G[i].dis < G[m].dis ) m = i;
}
}
return m;
}

void dijst ( int v , int n)
{
int i, k;
int min;
int *w = NULL;
int cw;

G[v].dis = 0;

while (1) {
min = find ( n );
if ( min < 0 ) {  /*Have no vertex to continue*/
break;
}

G[min].know = 1;
w = G[min].w; cw = G[min].cw;
for ( i = 0; i < cw; i++ ) {
if ( !G[ w[i] ].know ) {
if ( G[min].dis + G[min].ew[i] < G[ w[i] ].dis ) {
G[ w[i] ].dis = G[min].dis + G[min].ew[i];
G[ w[i] ].path = min;
}
}
}
}
}

void print_path ( int v )
{
if ( G[v].dis > 0 ) {
print_path ( G[v].path );
printf ("->v%d", v + 1 );
} else
printf ("v%d", v + 1 );
}

int main(int argc, char *argv[])
{
int n;
int i;

freopen ( "data.txt" , "r" , stdin );
dijst ( 0 , n );

for ( i = 0; i < n; i++ ) {
print_path ( i );
printf("\n");
}
return 0;
}```

7 2 1 2 3 1 2 3 3 4 10 2 5 5 0 4 4 2 2 4 2 5 8 6 4 1 6 6 0 1 5 1

0 条评论

• ### Linux 下从头再走 GTK+-3.0 (一)

原本由于项目需求在 Linux 下学习过一段时间的 GTK+2.0 图形开发，时隔一段时间，想真正深入学习一下 GTK 。

• ### VirtualBox: Effective UID is not root (euid=1000 egid=100 uid=1000 gid=100)

桌面上运行virtualbox出错: The virtual machine 'xp' has terminated unexpectedly during ...

• ### UVA-11600-Masud Rana

ACM模版 描述 ? ? 题解 image.png ? 保存六位小数…… 代码 #include <cstdio> #include <cstring> #in...

• ### 详解斯坦纳点及斯坦纳树及模版归纳总结

①什么是斯坦纳点？ 　　假设原来已经给定了个点，库朗等指出需要引进的点数至多为，此种点称为斯坦纳点。过每一斯坦纳点，至多有三条边通过。若为三条边，则它们两两交成...

• ### 拉格朗日插值

存在性和唯一性的证明以后再补。。。。 拉格朗日插值 拉格朗日插值，emmmm，名字挺高端的:joy: 它有什么应用呢？ 我们在FFT中讲到过 设n-1次多项式为...

• ### 学大伟业 国庆Day2

期望得分：30+100+0=130 实际得分：30+100+20=150 忍者钩爪 (ninja.pas/c/cpp) 【问题描述】 小Q是一名酷爱钩爪的忍者，...

• ### codeforces 573A （数论）

Limak is an old brown bear. He often plays poker with his friends. Today they we...