亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

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

發布時間:2020-07-09 09:11:59 來源:網絡 閱讀:655 作者:abc1550030776 欄目:編程語言

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

#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");
	}
}

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


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

下面是運行結果截圖:


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

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

西吉县| 宿州市| 汉川市| 紫金县| 夏邑县| 若羌县| 通许县| 吉木萨尔县| 罗山县| 丹棱县| 西青区| 绥芬河市| 南华县| 交口县| 东港市| 武平县| 东方市| 开江县| 萨迦县| 三台县| 南江县| 龙口市| 克东县| 元氏县| 福海县| 邻水| 旌德县| 财经| 息烽县| 汪清县| 通化市| 西畴县| 新宾| 资阳市| 鄂伦春自治旗| 太谷县| 澄迈县| 怀仁县| 汝阳县| 梓潼县| 雷山县|