专栏首页RainMark 的文章单源最短路径算法——Dijkstra算法

单源最短路径算法——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 read_graph ( void )
{
    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 );
    n = read_graph ();
    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

参考书籍:数据结构与算法分析(C语言描述第二版)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

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

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

    RainMark
  • UVA-11600-Masud Rana

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

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

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

    Angel_Kitty
  • 拉格朗日插值

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

    attack
  • 学大伟业 国庆Day2

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

    attack
  • codeforces 1077D(二分)

    dejavu1zz
  • codeforces 573A (数论)

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

    dejavu1zz
  • 2019二级C题库及解析(17)

    用户6755376

扫码关注云+社区

领取腾讯云代金券