自己寫的dijkstra算法的一個實現。

    之前在網上面看到這個算法還有提到如果使用堆的話會減低時間復雜度。然后就在想如果使用堆的話代碼應該如何實現。然后嘗試自己寫一個出來進行測試。測試了一副圖沒有問題。寫一篇博客記錄一下之前寫的代碼。

#define INF 99999999

struct SortNode {
	int NodeLabel;
	int PathLength;
};

void swap(SortNode *a, SortNode *b)
{
	SortNode temp = *b;
	*b = *a;
	*a = temp;
}

void max_heapify(SortNode arr[], int start, int end)
{
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end) {
		if (son + 1 <= end && (arr[son].PathLength > arr[son + 1].PathLength))
			son++;
		if (arr[dad].PathLength < arr[son].PathLength)
			return;
		else {
			swap(&arr[dad], &arr[son]);
			dad = son;
			son = dad * 2 + 1;
		}
	}
}

void Dijkstra(int **iPath, int nNodeNum, int *pOutputDistance, int **OutPutPath)
{
	if (nNodeNum == 1)
	{
		pOutputDistance[0] = 0;
		OutPutPath[0][0] = 0;
		return;
	}
	SortNode *heap = new SortNode[nNodeNum];
	for (int i = nNodeNum - 1; i >= 0; i--)
	{
		heap[i].NodeLabel = i;
		heap[i].PathLength = iPath[0][i];
		if (heap[i].PathLength < INF)
		{
			OutPutPath[i][0] = 0;
			OutPutPath[i][1] = i;
			if (2 < nNodeNum)
				OutPutPath[i][2] = 0;
		}
		max_heapify(heap, i, nNodeNum - 1);
	}
	for (int i = nNodeNum - 1; i > 0; i--)
	{
		swap(&heap[0], &heap[i]);
		max_heapify(heap, 0, i - 1);
		for (int j = i - 1; j > 0; j--)
		{
			if (iPath[heap[0].NodeLabel][heap[j].NodeLabel] < INF)
			{
				int newPathLength = heap[0].PathLength + iPath[heap[0].NodeLabel][heap[j].NodeLabel];
				if (newPathLength < (heap[j].PathLength))
				{
					heap[j].PathLength = newPathLength;
					OutPutPath[heap[j].NodeLabel][0] = OutPutPath[heap[0].NodeLabel][0];
					for (int k = 1; k < nNodeNum; k++)
					{
						if (OutPutPath[heap[0].NodeLabel][k] != 0)
						{
							OutPutPath[heap[j].NodeLabel][k] = OutPutPath[heap[0].NodeLabel][k];
						}
						else
						{
							OutPutPath[heap[j].NodeLabel][k] = heap[j].NodeLabel;
							if ((k + 1) < nNodeNum)
								OutPutPath[heap[j].NodeLabel][k + 1] = 0;
							break;
						}
					}
					max_heapify(heap, j, i - 1);
				}
			}
		}
	}
	for (int i = 0; i < nNodeNum; i++)
	{
		pOutputDistance[heap[i].NodeLabel] = heap[i].PathLength;
	}
	delete[] heap;
}

     以上就是我寫的實現代碼。自己寫了一個main函數來測試。

int main()
{
	int e[10][10];
	int n = 0, m = 0;
	scanf_s("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i == j)
				e[i][j] = 0;
			else
				e[i][j] = INF;
		}
	}
	int t1, t2, t3;
	for (int i = 0; i < m; i++)
	{
		scanf_s("%d %d %d", &t1, &t2, &t3);
		e[t1 - 1][t2 - 1] = t3;
	}
	int *a[10];
	for (int i = 0; i < 10; i++)
	{
		a[i] = e[i];
	}
	int dis[10];
	int outputPath[10][10];
	int *b[10];
	for (int i = 0; i < 10; i++)
	{
		b[i] = outputPath[i];
	}
	Dijkstra(a, n, dis, b);
	for (int i = 0; i < n; i++)
		printf("%d ", dis[i]);
	printf("\n");
	for (int i = 0; i < n; i++)
	{
		printf("%d", outputPath[i][0] + 1);
		for (int j = 1; j < n; j++)
		{
			if (outputPath[i][j] > 0)
			{
				printf(" -> %d", outputPath[i][j] + 1);
			}
			else
				break;
		}
		printf("\n");
	}
}

使用了網上面的一張圖來測試。

下面是運行結果截圖: