考虑 0 作为权重的变体 Dijkstra
Variation Dijkstra considering 0 as a weight
我正在尝试在邻接矩阵上实现 Dijkstra,其中 0 具有权重而不是“无连接”的含义。我正在为如何修改原始算法而苦苦挣扎,有什么线索可以帮助我找到出路吗?
实施:
#define V 3
int minDistance(int dist[], bool sptSet[]){
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void dijkstra(int graph[V][V], int src){
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
}
例如,如果我输入:
0, 0, 0
1, 2, 1
2, 9, 3
最小路径长度应为 0,而我得到的是 2147483647,即 INT_MAX。
源是节点 0,目标是所有其他节点。
在您提供的实现中,更新节点距离的条件是:
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
第二部分是导致您的代码在查找成本为零的边时跳过的部分:
graph[u][v]
我假设您的代码是用 C++ 编写的。因此,如果值不为零,此检查意味着 true,否则 false。您需要更新条件以删除此部分:
if (!sptSet[v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
在这种情况下,算法应该可以正常工作。
如果你使用了这个更新,仍然需要指明没有边缘的情况,那么你可以将它的值设置为INT_MAX而不是零。
我正在尝试在邻接矩阵上实现 Dijkstra,其中 0 具有权重而不是“无连接”的含义。我正在为如何修改原始算法而苦苦挣扎,有什么线索可以帮助我找到出路吗? 实施:
#define V 3
int minDistance(int dist[], bool sptSet[]){
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void dijkstra(int graph[V][V], int src){
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
}
例如,如果我输入:
0, 0, 0
1, 2, 1
2, 9, 3
最小路径长度应为 0,而我得到的是 2147483647,即 INT_MAX。
源是节点 0,目标是所有其他节点。
在您提供的实现中,更新节点距离的条件是:
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
第二部分是导致您的代码在查找成本为零的边时跳过的部分:
graph[u][v]
我假设您的代码是用 C++ 编写的。因此,如果值不为零,此检查意味着 true,否则 false。您需要更新条件以删除此部分:
if (!sptSet[v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
在这种情况下,算法应该可以正常工作。
如果你使用了这个更新,仍然需要指明没有边缘的情况,那么你可以将它的值设置为INT_MAX而不是零。