dijkstra算法(单源最短路径)

单源最短路径是求解给定一个起点到其他所有的点的最短距离。

适用的范围:有向图、边的权值没有负数

洛谷测试链接

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#include <limits.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 100000//节点的最大个数

typedef struct {//堆中存放的变量类型
	int t;//表示从源点到t点
	int d;//源点到t点的距离
}p;

typedef p ELEMENT;

//小根堆的ADT接口
typedef struct heap {
	ELEMENT* data;//´æ·ÅÔªËصÄÊý×é 
	int size;//×îС¶ÑÖеÄÔªËظöÊý 
	int maxSize;//¶ÑÖÐ×î¶àÄܹ»ÈÝÄɵÄÔªËظöÊý 
}minHeap, * MinHeap;

MinHeap createMinHeap(int n);//´´½¨Ò»¸ö×î¶àÄܹ»ÈÝÄÉn¸öÔªËصÄ×îС¶Ñ 
int MinHeapSize(MinHeap h);//·µ»Ø×îС¶ÑµÄÔªËظöÊý 
bool isMinHeapFull(MinHeap h);//ÅжÏ×îС¶ÑÊDz»ÊÇÂúÁË 
bool addMinHeap(MinHeap h, ELEMENT item);//Íù×îС¶ÑÀïÃæÌí¼ÓÔªËØitem
ELEMENT deleteMinHeap(MinHeap h);//µ¯³ö×îС¶ÑµÄ¶Ñ¶¥ÔªËØ 
void MinHeapInsert(MinHeap h, int index);//ÔÚ×îС¶ÑindexλÖÃнøÀ´Ò»¸öÔªËØ£¬ËùÒÔÒªÏòÉϵ÷Õû£¬À´ÈöÑÈÔÈ»ÊÇÒ»¸ö×îС¶Ñ 
void MinHeapify(MinHeap h, int index);//ÔÚ×îС¶ÑindexλÖõÄÔªËرäСÁË£¬ËùÒÔÏòϵ÷Õû¶Ñ£¬À´ÈöÑÈÔÈ»ÊÇÒ»¸ö×îС¶Ñ 
bool isMinHeapEmpty(MinHeap h);//ÅжÏ×îС¶Ñ¿ÕÁËûÓÐ 
void swap(MinHeap h, int i, int j);//½»»»×îС¶ÑÖÐiºÍjλÖõÄÔªËØ 
int MinHeapCompare(ELEMENT a, ELEMENT b);//»ùÓÚijÖйæÔòÀ´±È½Ï,ÀàËÆÓë±È½ÏÆ÷ 
void freeMinHeap(MinHeap h);//ÊÍ·Å×îС¶ÑµÄ¿Õ¼ä 
ELEMENT peekMinHeap(MinHeap h);//µÃµ½×îС¶ÑÖеĶѶ¥ÔªËØ 

int n;//节点的数量
int m;//边的数量
int s;//源点
//链式前向星
int head[N + 1];//每个节点的头边
int next[2 * N + 1];//每条边的下一边
int to[2 * N + 1];//每条边指向的节点
int w[2 * N + 1];//每条边对应的权重
int cnt = 1;//边的编号从1开始
int distance[N + 1];//从源点到每个点的距离
bool v[N + 1];//标记是不是已经找到最短路径
int b[3];//存放输入的信息

int main(int argc, char* argv[])
{
	sc("%d%d%d", &n, &m, &s);//读入节点数和边数和源点的位置

	//链式前向星建图
	for (int i = 0; i < m; i++) {
		sc("%d%d%d", b, b + 1, b + 2);

		next[cnt] = head[b[0]];//新的边指向老的头边
		to[cnt] = b[1];//新的边指向的节点是b[1]
		w[cnt] = b[2];//边对应的权重是b[2]
		head[b[0]] = cnt++;//更新节点的头边
	}

	for (int i = 1; i <= n; i++) {//初始话距离数组，用INT_MAX表示无穷大，节点的编号从1开始
		distance[i] = INT_MAX;
	}

	distance[s] = 0;//源点到源点的距离为0

	p t = { s, 0 };//对应的变量

	MinHeap h = createMinHeap(m);//创建一个有m大小的小根堆

	addMinHeap(h, t);//把变量放入小根堆

	while (!isMinHeapEmpty(h)) {//小根堆不为空
		p temp = deleteMinHeap(h);//弹出小根堆的堆顶元素

		if (v[temp.t] == 0) {//如果源点到temp.t的点的边没有被访问过，那么才继续
			for (int j = head[temp.t]; j; j = next[j]) {//遍历访问
				if (v[to[j]] == 0 && (temp.d + w[j] < distance[to[j]])) {
					distance[to[j]] = temp.d + w[j];
					p t1 = { to[j], distance[to[j]] };
					addMinHeap(h, t1);
				}
			}
			v[temp.t] = 1;//刚刚弹出了，所以访问了，就置为1
		}
	}

	//输出起点到所有点的最短距离
	for (int i = 1; i <= n; i++) {
		pr("%d ", distance[i]);
	}

	freeMinHeap(h);

	return 0;
}

MinHeap createMinHeap(int n)
{
	MinHeap h = (MinHeap)malloc(sizeof(minHeap));//¿ª±ÙÒ»¸ö×îС¶Ñ 

	h->data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//¿ª±ÙÒ»¸ön¸ö¿Õ¼äµÄELEMENTÊý×é 
	h->size = 0;//³õʼ»¯×îС¶ÑÔªËØÊÇ0 
	h->maxSize = n;//×îС¶ÑÄÜ´æ·Å×î´óÔªËصĸöÊýÊÇn 

	return h;//·µ»Ø×îС¶Ñ 
}
int MinHeapSize(MinHeap h)
{
	return h->size;//·µ»Ø×îС¶ÑÖеÄÔªËظöÊý 
}
bool isMinHeapFull(MinHeap h)
{
	return h->size == h->maxSize;//Èç¹û×îС¶ÑÖеÄÔªËظöÊýµÈÓÚÄܹ»ÈÝÄɵÄ×î´óÔªËظöÊý£¬ÄÇôÂúÁË 
}
bool addMinHeap(MinHeap h, ELEMENT item)
{
	if (isMinHeapFull(h)) {//Èç¹û×îС¶ÑÒѾ­ÂúÁË£¬ÄÇô¾Í²»ÄÜÌí¼ÓÔªËØÁË£¬·µ»Øfalse 
		return false;
	}

	h->data[h->size] = item;//°Ñitem·ÅÔÚ×î϶ÑÖÐÔªËظöÊýµÄϱêÖÐ,ÒòΪԪËظöÊýµÄϱê¾ÍÊÇÒª·ÅµÄλÖà 
	MinHeapInsert(h, h->size);//ÒòΪ¸Õ¸ÕнøÀ´Ò»¸öÔªËØ£¬ËùÒÔÏëÈöѼÌÐø±£³Ö×îС¶Ñ£¬ÄÇô¾ÍÐèÒªÏòÉϵ÷Õû¶Ñ 
	h->size++;//ÈÃ×îС¶ÑÖеÄÔªËظöÊý¼ÓÒ» 

	return true;//Ìí¼Ó³É¹¦·µ»Øtrue 
}
ELEMENT deleteMinHeap(MinHeap h)
{
	if (isMinHeapEmpty(h)) {//Èç¹û×îС¶ÑÖÐûÓÐÔªËØ£¬ÄÇô²»ÄܽøÐÐɾ³ý£¬Î¥·¨·µ»ØÒ»¸öÌض¨µÄÖµ£¬¼´ERROR 
		p t = { -1, -1 };
		return t;
	}

	ELEMENT ans = h->data[0];//·µ»Ø×îС¶ÑÖеĶѶ¥ÔªËØ 
	swap(h, 0, --h->size);//°Ñ×îС¶ÑÖеÄ×îºóÒ»¸öÔªËØÓë¶Ñ¶¥ÔªËؽøÐн»»»£¬²¢ÇÒÈöÑÖÐÔªËؼõÒ»£¬ÄÇô¾Í·ÃÎʲ»µ½¸Õ¸Õ±»É¾³ýµÄÔªËØÁË¡£ 
	MinHeapify(h, 0);//ϱê0λÖõÄÔªËرä´óÁË£¬ÄÇôΪÁ˼ÌÐø±£³ÖÒ»¸ö×îС¶Ñ£¬¾ÍÒªÏòϵ÷Õû 

	return ans;//·µ»Ø×îС¶ÑÖеĶѶ¥ÔªËØ 
}
void MinHeapInsert(MinHeap h, int index)//indexλÖõÄÊýÏòÉϵ÷ÕûС¸ù¶Ñ 
{
	while (MinHeapCompare(h->data[index], h->data[(index - 1) / 2]))//Èç¹ûϱêindexµÄֵСÓÚËüµÄ¸¸½Úµã 
	{
		swap(h, index, (index - 1) / 2);//ϱêindexµÄÖµºÍËüµÄ¸¸½ÚµãµÄÖµ½»»» 
		index = (index - 1) / 2;//¸üÐÂindexµÄλÖà 
	}
}
bool isMinHeapEmpty(MinHeap h)
{
	return !h->size;//Èç¹û×îС¶ÑÖеÄÔªËØÊÇ0¸ö£¬ÄÇô¾ÍÊÇ¿Õ£¬ÓÐÔªËؾͲ»ÊÇ¿Õ 
}
void swap(MinHeap h, int i, int j)
{
	ELEMENT t = h->data[i];
	h->data[i] = h->data[j];
	h->data[j] = t;
}
void MinHeapify(MinHeap h, int index)
{
	int left = 2 * index + 1;//¼ÆËãϱêindexµÄ×óº¢×Ó 

	while (left < h->size) {//Èç¹ûÓк¢×Ó 
		int lessest = left + 1 < h->size && MinHeapCompare(h->data[left + 1], h->data[left]) ? left + 1 : left;//Èç¹ûÓÐÓÒº¢×Ó²¢ÇÒÓÒº¢×ÓСÓÚ×óº¢×Ó£¬ÄÇôº¢×ÓÖÐ×îСµÄ¾ÍÊÇÓÒº¢×Ó£¬·ñÔò¾ÍÊÇ×óº¢×Ó 

		lessest = MinHeapCompare(h->data[index], h->data[lessest]) ? index : lessest;//Èç¹û¸¸Ç×½Úµã±Èº¢×ÓÖÐ×îСµÄ»¹ÒªÐ¡£¬ÄÇô×îСµÄ½Úµã¾ÍÊǸ¸½Úµã£¬²»È»×îСµÄ½Úµã¾ÍÊǺ¢×ÓÖÐ×îСµÄ½Úµã 

		if (lessest == index) {//Èç¹û×îСµÄ½ÚµãÊǸ¸½Úµã£¬ÄÇô²»ÓüÌÐøÁË£¬ÒѾ­ÊÇ×îС¶ÑÁË 
			break;
		}

		swap(h, index, lessest);//Óë×îСµÄº¢×Ó½øÐн»»» 
		index = lessest;//¸üÐÂindexϱ꣬ÒòΪ¸Õ¸Õ½»»»ÁË 
		left = 2 * index + 1;//ÖØмÆËãϱêindexµÄ×óº¢×Ó 
	}
}
int MinHeapCompare(ELEMENT a, ELEMENT b)
{
	return a.d < b.d;//Ö±½Ó½øÐÐÖµµÄ±È½Ï 
}
void freeMinHeap(MinHeap h)
{
	free(h->data);//ÏÈÊÍ·Å×îС¶Ñ´æ·ÅÔªËصĿռä 
	free(h);//ÔÙÊÍ·Å×îС¶ÑµÄ¿Õ¼ä 
}
ELEMENT peekMinHeap(MinHeap h)
{
	if (isMinHeapEmpty(h)) {//×îС¶ÑÀïÃæûÓÐÔªËØÄÇô£¬²Ù×÷Î¥·¨£¬·µ»ØÌض¨Öµ 
		p t = { -1, -1 };
		return t;
	}

	ELEMENT ans = deleteMinHeap(h);//µ¯³ö×îС¶ÑµÄ¶Ñ¶¥ 

	addMinHeap(h, ans);//ÔÙ·ÅÈë×îС¶Ñ£¬ÒÔ´ËÀ´ÊµÏÖ´úÂ븴Óà 

	return ans;//·µ»Ø×îС¶ÑµÄ¶Ñ¶¥ÔªËØ 
}

时间复杂度是O(m * logm)，m为边的数量，这是通过最小堆来优化的。

本质是通过之前求出的最短路和现在有的最短路来比较，然后更新最短路，一旦从堆中弹出，那么起点到那个点的最短路也就确定了，那么之后碰到弹出的就不管了，然后再利用已知的最短路求其他点的最短路