while (1) { int min = getDijkstraMinimum(visit, dis, matrix->size); if (min == -1) break; visit[min] = VISIT_STATE_MARK; for (int to = 0; to < matrix->size; ++to) { if (visit[to] == VISIT_STATE_VOID) { WEIGHT_TYPE weight = matrix->data[min][to]; // 两点间存在邻接关系 if (weight < INFINITY) { //松弛成功 if ((dis[min] + weight) < dis[to]) { dis[to] = dis[min] + weight; path[to] = min; } } } } }
时间: 2023-07-14 18:12:19 浏览: 28
这是一个基于 Dijkstra 算法实现的最短路径算法,用于求解带权有向图或无向图中两个节点之间的最短路径。它通过不断选择当前最短的节点来进行松弛操作,更新到达其他节点的最短距离和路径。
在代码中,变量 visit 表示当前节点是否已被访问过,dis 表示从源节点到各个节点的最短距离,path 表示最短路径上到达当前节点的前一个节点。getDijkstraMinimum 函数用于返回当前未访问节点中距离源节点最近的节点,如果不存在这样的节点则返回 -1。
在主循环中,先找到距离源节点最近的未访问节点,将其标记为已访问。然后遍历所有未访问节点,对于两点间存在邻接关系的节点,进行松弛操作,更新到达该节点的最短距离和路径。
该算法的时间复杂度为 O(n^2),可以通过堆优化优化到 O(nlogn)。
相关问题
bool ff(int number,int size)//首次适应算法 { pNod temp= new Free_Node; Free_Node *p=headNode->next; //从首节点开始 temp->date.number=number; temp->date.size=size; temp->date.flag=BUSY; while(p) { if (p->date.flag==FREE && p->date.size == size )//请求大小刚好满足 { p->date.flag=BUSY; p->date.number=number; return true; } if (p->date.flag==FREE && p->date.size>size)//说明还有其他的空闲区间 { temp->next=p; temp->prior=p->prior; temp->date.begin_address=p->date.begin_address; p->prior->next=temp; p->prior=temp; p->date.begin_address=temp->date.begin_address+temp->date.size;//空闲分区开始地址+此次分配的空间 p->date.size-=size; //分配空闲作业 return true; } p=p->next; } return false; }改为最差适应算法
将该函数改为最差适应算法的代码如下所示:
```
bool wf(int number, int size) {
Free_Node* temp = new Free_Node;
Free_Node* p = headNode->next;
Free_Node* worst_node = nullptr; // 最差适应算法需要记录最大空闲区间
int max_size = -1; // 最差适应算法需要记录最大空闲区间的大小
temp->date.number = number;
temp->date.size = size;
temp->date.flag = BUSY;
while (p) {
if (p->date.flag == FREE && p->date.size >= size) { // 如果空闲区间大小满足要求
if (p->date.size > max_size) { // 找到更大的空闲区间
max_size = p->date.size;
worst_node = p;
}
}
p = p->next;
}
if (worst_node) { // 找到了空闲区间
temp->next = worst_node;
temp->prior = worst_node->prior;
temp->date.begin_address = worst_node->date.begin_address;
worst_node->prior->next = temp;
worst_node->prior = temp;
worst_node->date.begin_address = temp->date.begin_address + temp->date.size;
worst_node->date.size -= size;
worst_node->date.flag = FREE;
return true;
}
return false;
}
```
需要注意的是,最差适应算法需要记录最大空闲区间,因此在遍历空闲区间时需要记录当前的最大空闲区间。
Node *selectSort(Node *head){ Node *p = head, *q = NULL, *min = NULL, *tmp = NULL; while (p != NULL) { min = p; q = p->next; while (q != NULL) { if (q->data < min->data) { min = q; } q = q->next; } if (min != p) { tmp = min->data; min->data = p->data; p->data = tmp; } p = p->next; } return head; }为以上代码添加注释
/* 选择排序函数,参数为链表头指针,返回排序后的链表头指针 */
Node *selectSort(Node *head){
Node *p = head, *q = NULL, *min = NULL, *tmp = NULL; // 定义指针p, q, min, tmp,初始化为NULL
while (p != NULL) { // 当p不为NULL时,继续执行循环
min = p; // 将min指针指向p节点
q = p->next; // 将q指针指向p节点的下一个节点
while (q != NULL) { // 当q不为NULL时,继续执行循环
if (q->data < min->data) { // 如果q节点的data成员比min节点的data成员小
min = q; // 将min指针指向q节点
}
q = q->next; // 将q指针指向下一个节点
}
if (min != p) { // 如果min节点不等于p节点
tmp = min->data; // 将tmp指针指向min节点的data成员
min->data = p->data; // 将min节点的data成员赋值为p节点的data成员
p->data = tmp; // 将p节点的data成员赋值为tmp指针指向的值
}
p = p->next; // 将p指针指向下一个节点
}
return head; // 返回排序后的链表头指针
}
相关推荐
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)