基于邻接表的Dijkstra算法C++实现补全求助

Alright, let's break down how to implement Dijkstra's Algorithm with your adjacency list setup step by step. I'll fix the issues in your existing code and explain each part clearly.

Step 1: Fix Basic Definitions and Variable Setup #

First, your INFINITE definition is problematic (-1 can be confused with an invalid distance, but all edge weights here are positive integers). Let's update that and include the necessary header:

#include <climits> // For INT_MAX
#define INFINITE INT_MAX

Instead of using fixed-size arrays for distance and state, use vector since your graph size is dynamic (stored in a vector<GraphNode>). This avoids issues with non-standard variable-length arrays in C++.

Step 2: Correct Initialization of Distance and State #

In your DijkstrasAlgorithm function, you need to properly initialize the distance and state vectors based on the source node's actual index, not just hardcoding index 0. Here's the corrected initialization:

void Graph::DijkstrasAlgorithm(char sourcenode) {
    int n = adjlist.size();
    vector<int> distance(n, INFINITE);
    vector<char> state(n, 't'); // 't' = temporary (unprocessed), 'p' = permanent (processed)
    
    // Find the index of the source node in the adjacency list
    int sourceIdx = -1;
    for (int i = 0; i < n; i++) {
        if (adjlist[i].key == sourcenode) {
            sourceIdx = i;
            break;
        }
    }
    if (sourceIdx == -1) {
        cout << "Source node not found in graph!" << endl;
        return;
    }
    
    // Initialize source node's distance to 0
    distance[sourceIdx] = 0;

Step 3: Core Dijkstra Loop #

The main logic is to repeatedly select the unprocessed node with the smallest current distance, mark it as processed, then relax all its outgoing edges. Add this loop after initialization:

int processedCount = 0;
    while (processedCount < n) {
        // Step 1: Find the temporary node with the minimum distance
        int minDist = INFINITE;
        int u = -1;
        for (int i = 0; i < n; i++) {
            if (state[i] == 't' && distance[i] < minDist) {
                minDist = distance[i];
                u = i;
            }
        }
        
        // If no more reachable nodes, exit the loop
        if (u == -1) break;
        
        // Mark node u as permanent (processed)
        state[u] = 'p';
        processedCount++;
        
        // Step 2: Relax all edges from u to its neighbors
        Node* current = adjlist[u].listpointer;
        while (current != nullptr) {
            // Find the index of the neighbor node (current->key)
            int v = -1;
            for (int i = 0; i < n; i++) {
                if (adjlist[i].key == current->key) {
                    v = i;
                    break;
                }
            }
            if (v == -1) {
                current = current->next;
                continue;
            }
            
            // Relaxation step: update distance if going through u is shorter
            if (state[v] == 't' && distance[u] != INFINITE && distance[u] + current->distance < distance[v]) {
                distance[v] = distance[u] + current->distance;
            }
            current = current->next;
        }
    }

Step 4: Add Output for Shortest Paths #

After computing the distances, add code to print the results in a readable format:

// Print the shortest paths from the source node
    cout << "Shortest paths from node " << sourcenode << ":" << endl;
    for (int i = 0; i < n; i++) {
        cout << "To node " << adjlist[i].key << ": ";
        if (distance[i] == INFINITE) {
            cout << "Unreachable" << endl;
        } else {
            cout << distance[i] << endl;
        }
    }
}

Step 5: Fix Input Reading (Critical Missing Part!) #

Your original main function didn't read the input file to populate the graph. Let's add that to build the graph correctly:

int main() { // Use standard int main() instead of old-style main
    ifstream inputFile("input.txt"); // Replace with your actual input file path
    if (!inputFile.is_open()) {
        cout << "Failed to open input file!" << endl;
        return 1;
    }
    
    string line;
    getline(inputFile, line);
    istringstream iss(line);
    
    char from, to;
    int dist;
    vector<char> uniqueNodes;
    
    // First, collect all unique nodes and add them to the graph
    while (iss >> from >> to >> dist) {
        // Add 'from' node if not already present
        bool found = false;
        for (char c : uniqueNodes) {
            if (c == from) {
                found = true;
                break;
            }
        }
        if (!found) {
            uniqueNodes.push_back(from);
            mygraph.AddNewGraphNode(from);
        }
        // Add 'to' node if not already present
        found = false;
        for (char c : uniqueNodes) {
            if (c == to) {
                found = true;
                break;
            }
        }
        if (!found) {
            uniqueNodes.push_back(to);
            mygraph.AddNewGraphNode(to);
        }
        // Add the directed edge
        mygraph.AddNewEdgeBetweenGraphNodes(from, to, dist);
    }
    
    inputFile.close();
    
    // Optional: Verify the graph structure
    cout << "Graph adjacency list:" << endl;
    mygraph.PrintAllGraphNodesWithCosts();
    cout << endl;
    
    // Run Dijkstra's algorithm from node A
    mygraph.DijkstrasAlgorithm('A');
    
    return 0;
}

Key Notes About the Fixes: #

• Infinite Distance: Using INT_MAX instead of -1 avoids confusion between unreachable nodes and valid distances (since all edge weights are positive).
• Vector Usage: Dynamic vectors handle variable graph sizes safely, unlike fixed arrays.
• Node Index Lookup: We added helper loops to map node keys (like 'A', 'B') to their indices in the adjacency list.
• Relaxation Step: For each processed node, we check all neighbors and update their distance if a shorter path exists through the current node.
• Input Handling: The added code reads the input line, collects unique nodes, and builds the adjacency list correctly.

When you run the program with your input line:

A B 10 A C 5 B A 3 B C 2 C A 4 C B 1

It will output:

Graph adjacency list:
From Node A: 
to node C dist: 5 
to node B dist: 10 
From Node B: 
to node C dist: 2 
to node A dist: 3 
From Node C: 
to node B dist: 1 
to node A dist: 4 

Shortest paths from node A:
To node A: 0
To node B: 6
To node C: 5

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