Dijkstra算法：
问题：给定一个带权图G=(V,E,w),找到从给定源点u0到其他各点的最短路径。
Step:
求带权图G(V,E)的点v0到其他各点的最短路径；
1.初始时，S={v0},U={v1,v1…vn};点v0到其他点的最短距离为<v0,vi>(i=1,2,3…n)的权；将v0到其他各点vi的最短路径中vi的前驱动点初始化为v0;
2,从U中选取u，使得当前v0到u的最短路径的距离小于v0到U中其他各点的最短路径的距离，将u加入S,并将u从U中删除
3,遍历每个在U中的点s，如果以u为中介点的最短路径的距离小于当前存储的距离，更新从v0到s的最短路径的距离，并将v0到s的最短路径的s的前驱动点更新为u;
4,重复2,3直到U为空；

绿色顶点表示源点到该顶点的距离已确定 蓝色顶点表示要加入集合S的顶点 {dis,v},v表示前驱动点，dis表示源点到该顶点的最短距离

代码：

#include <stdio.h>
#define INF 10000000
#define MaxSize 50
int graph[MaxSize][MaxSize];  //MaxSize为最大顶点数
int dis[MaxSize];             //dis[i]为源点到顶点i的最短距离
int visit[MaxSize];            //visit[i]标记顶点i的最短路径是否已求出visit[i] == 1表示已求出
int prevetrix[MaxSize];       //前驱动点
void dij(int n)
{    
    int count = 0;          //count是已求出最短路径的顶点数目
    visit[0] = 1;    
    prevetrix[0] = 0;    
    count++;    
    for (int i = 1; i < n; i++)    //初始化
    {        
        dis[i] = graph[0][i];        
        prevetrix[i] = 0;    
    }    
    while (count < n)    
    {        
        int min = INF, target_index;        
        for (int i = 1; i < n; i++)        
        {            
            if (visit[i] == 0 && min > dis[i])         //找到距离源点最短的顶点target_index
            {                
                min = dis[i];                
                target_index = i;            
            }        
        }        
        visit[target_index] = 1;        
        count++;        
        for (int i = 1; i < n; i++)        
        {            
            if (visit[i] == 0 && dis[target_index] + 
            graph[target_index][i] < dis[i])            //更新
            {                
                dis[i] = dis[target_index] + graph[target_index][i];
                prevetrix[i] = target_index;            
            }        
        }    
    }
}
int main()
{    
    int n, m;    
    scanf("%d %d", &n, &m);    //n为顶点数,m为边数
    int a, b, w, path[n];    
    for (int i = 0; i < n; i++)    
    {        
        for (int j = 0; j < n; j++)        
        {            
            graph[i][j] = INF;        
        }    
    }    
    for (int i = 0; i < m; i++)    
    {        
        scanf("%d %d %d", &a, &b, &w);        //a为起始点,b为终点,w为边a->b的权重
        graph[a][b] = w;    
    }     
    dij(n);    
    printf("\n\n");    
    for (int i = 1; i < n; i++)    
    {        
        if (dis[i] == INF)        
        {            
            printf("顶点0到顶点%d没有最短路径\n", i);        
        }        
        else        
        {            
    	    printf("顶点0到顶点%d有长为%d的最短路径：", i,dis[i]);            
    	    int cur = i, index = 0;            
            path[index] = cur;            
            while (1)            
            {                
                path[index + 1] = prevetrix[path[index]];                
                if (path[index + 1] == 0)                    
                    break;                
                index++;            
            }            
            for (int j = index + 1; j > 0; j--)            
            {                
                printf("%d->", path[j]);            
            }            
            printf("%d\n", path[0]);        
        }    
    }
}
复制

输入：
6 8
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 5 60
4 3 20
输出：
顶点0到顶点1没有最短路径
顶点0到顶点2有长为10的最短路径：0->2
顶点0到顶点3有长为50的最短路径：0->4->3
顶点0到顶点4有长为30的最短路径：0->4
顶点0到顶点5有长为60的最短路径：0->4->3->5
复制

注意：diskstra算法只能求边权值为非负值的情况

推荐内容