C++ Dijkstra算法实现中Vector下标越界问题及GetIndex函数疑问

Hey there! Let's break down the issues you're facing with your Dijkstra implementation step by step—since this is for a university assignment, I'll focus on explaining the root problems and guiding you to fix them instead of giving copy-paste code.

First: Let's Diagnose the Vector Out-of-Bounds Error #

Your reported crash in the LeastDistance for loop likely stems from a few key issues, plus some logic flaws that are breaking the algorithm's flow:

1. Unvalidated Input Risks Invalid Indices #

Your GetStartNode function doesn't check if the user's input is actually between 'A' and 'E'. If someone enters a character like 'F' or 'a', your GetIndex function will return an integer outside the range of your hnode vector (which only has 5 elements, indices 0-4). Accessing hnode[i] with this invalid index immediately triggers an out-of-bounds exception.

2. LeastDistance Has Critical Logic Flaws #

Right now, this function isn't implementing the core of Dijkstra's correctly, which can lead to unexpected behavior (including potential secondary out-of-bounds errors):

• You're checking if the current node (hnode[i].Visited) is unvisited, but you should be checking if the adjacent node is unvisited.
• When you find a "smallest" adjacent node, you mark the current node as visited (hnode[idx].Visited = true) instead of marking the adjacent node you just selected. This breaks the algorithm's tracking of which nodes have been processed.
• If all adjacent nodes are already visited, your function will return the original input node, sending your Dijkstra loop into an infinite cycle—this can lead to other runtime errors down the line.

3. Uninitialized weight and path Vectors #

In your printAdjMatrix function, you try to access weight[i] and iterate over path, but these vectors are never populated or resized. Their size is 0, so any access to weight[i] will trigger another out-of-bounds error, even if you fix the LeastDistance issue.

4. Broken INF Macro Definition #

Your line #define INF = 9999; is invalid syntax for a macro. Macro definitions don't use equals signs—this should be #define INF 9999. The current line will cause compilation or logic errors when you try to use INF later.

Fix Steps to Guide You #

Here's how to address these issues without writing code for you:

1. Add input validation to GetStartNode: After reading the user's input, check if it's between 'A' and 'E'. If not, prompt them to re-enter a valid node. This ensures GetIndex always returns a valid index for hnode.
2. Rewrite LeastDistance logic:
   • For each adjacent node in hnode[i].nodes, use GetIndex to find its position in the hnode vector.
   • Check if that adjacent node's Visited flag is false before considering its cost.
   • When you select the smallest valid adjacent node, mark that adjacent node (not the current one) as visited.
   • Add a check to handle cases where no unvisited adjacent nodes exist (to avoid infinite loops).
3. Initialize and populate weight and path: In your Dijkstra function, you need to track the shortest distance from the start node to each other node (store these in weight) and build the path for each destination (store these in path). Make sure to resize these vectors to match the number of nodes in hnode at initialization.
4. Fix the INF macro: Correct the syntax to remove the equals sign and semicolon.

内容的提问来源于stack exchange，提问作者Thefoilist