校园垃圾箱最佳布局：Dijkstra算法实现

观察现在校园内的垃圾箱的布局，如果在每条主干道之间布置的垃圾箱不能超过两个（两头各安置一个），那么又应该如何布局垃圾箱，使得行人手提垃圾袋的距离最小？

已知只有一个行人从A02（-600，200）到A05（200，500），主干道从左端（-100，400）到右端的（500，400），使用C语言，用Dijkstra算法，写出如何布局垃圾桶才能使行人手提垃圾袋的距离最小，两个垃圾桶只能在主干道上，写出详细代码和结果，结果是两个垃圾桶的坐标。

思路:

首先，我们可以将校园内的地图抽象成一个图，其中每个交叉路口为一个节点，两个交叉路口之间的道路为一条边，边的权值为两个交叉路口之间的距离。然后，我们可以使用Dijkstra算法求出从A02到A05的最短路径。在此基础上，我们可以考虑如何布局垃圾箱。

根据题目要求，每条主干道之间最多只能有两个垃圾箱，因此我们可以在主干道上选择两个节点作为垃圾箱的位置，使得这两个节点到最短路径的距离之和最小。

具体实现步骤:

定义一个数组dist，表示每个节点到A02的最短距离。2. 从左端点开始，依次遍历每个节点，找到距离A02最近的两个节点，作为垃圾箱的位置。3. 计算这两个节点到A05的距离之和，并记录下最小值。4. 输出最小值对应的两个节点的坐标，即为垃圾箱的位置。

**代码实现:**c#include <stdio.h>#include <stdlib.h>#include <math.h>

#define MAX_NODE 1000#define INF 0x3f3f3f3f

struct node { int x, y; // 节点坐标 int dist; // 到A02的最短距离 int visited; // 是否已遍历 int prev; // 前驱节点编号};

struct edge { int u, v; // 边的两个节点编号 int w; // 边的权值};

struct node nodes[MAX_NODE];struct edge edges[MAX_NODE*MAX_NODE];int n_node, n_edge;

int cmp(const void *a, const void *b) { return ((struct edge *)a)->w - ((struct edge *)b)->w;}

void add_node(int x, int y, int dist) { nodes[n_node].x = x; nodes[n_node].y = y; nodes[n_node].dist = dist; nodes[n_node].visited = 0; nodes[n_node].prev = -1; n_node++;}

void add_edge(int u, int v) { edges[n_edge].u = u; edges[n_edge].v = v; edges[n_edge].w = sqrt(pow(nodes[u].x-nodes[v].x, 2) + pow(nodes[u].y-nodes[v].y, 2)); n_edge++;}

void dijkstra(int src) { int i, u, v; for (i = 0; i < n_node; i++) { nodes[i].dist = INF; nodes[i].visited = 0; nodes[i].prev = -1; } nodes[src].dist = 0; while (1) { u = -1; for (i = 0; i < n_node; i++) { if (!nodes[i].visited && (u == -1 || nodes[i].dist < nodes[u].dist)) { u = i; } } if (u == -1 || nodes[u].dist == INF) { break; } nodes[u].visited = 1; for (i = 0; i < n_edge; i++) { v = edges[i].v; if (edges[i].u == u && nodes[v].dist > nodes[u].dist + edges[i].w) { nodes[v].dist = nodes[u].dist + edges[i].w; nodes[v].prev = u; } v = edges[i].u; if (edges[i].v == u && nodes[v].dist > nodes[u].dist + edges[i].w) { nodes[v].dist = nodes[u].dist + edges[i].w; nodes[v].prev = u; } } }}

int main(void) { int i, j, x, y, dist; // 添加节点 add_node(-600, 200, INF); // A02 add_node(-100, 400, INF); add_node(200, 400, INF); add_node(500, 400, INF); // A05 add_node(-100, 200, INF); add_node(200, 200, INF); add_node(-100, 0, INF); add_node(200, 0, INF); // 添加边 add_edge(0, 1); add_edge(0, 4); add_edge(1, 2); add_edge(2, 3); add_edge(4, 5); add_edge(4, 6); add_edge(5, 7); add_edge(6, 7); // 计算最短路径 dijkstra(0); // 找到最佳垃圾箱位置 int min_dist = INF; int x1, y1, x2, y2; for (i = 1; i <= 3; i++) { // 选定主干道上的三个节点 for (j = i+1; j <= 4; j++) { int d1 = nodes[i].dist; int d2 = nodes[j].dist; int d3 = nodes[nodes[i].prev].dist + nodes[nodes[j].prev].dist + sqrt(pow(nodes[i].x-nodes[j].x, 2) + pow(nodes[i].y-nodes[j].y, 2)); int dist = d1 + d2 + d3; if (dist < min_dist) { min_dist = dist; x1 = nodes[i].x; y1 = nodes[i].y; x2 = nodes[j].x; y2 = nodes[j].y; } } } printf('最小距离：%d ', min_dist); printf('垃圾箱1坐标：%d,%d ', x1, y1); printf('垃圾箱2坐标：%d,%d ', x2, y2); return 0