如何初始化图中两节点间权重？Dijkstra算法实现遇阻

Hey there! Let's work through the add_edge problem you're hitting with your Dijkstra algorithm. Since you can't use vector, we're leaning into pointer-linked structures for the graph—let's start by filling in the gaps that are likely causing your weight initialization issues.

First, let's confirm the missing ListNode class definition. This should hold the adjacent node pointer and the edge weight, which is probably where things are breaking if it's not set up right:

class ListNode {
public:
    Node* neighbor; // Pointer to the adjacent node
    int weight;     // Weight of the edge between nodes
    ListNode* next; // Next node in the adjacency list
    // Constructor to initialize edge details
    ListNode(Node* n, int w) : neighbor(n), weight(w), next(nullptr) {}
};

Next, let's address common pitfalls in the add_edge function and write a robust implementation:

Key Issues to Fix #

• Missing Node Validation: You need to make sure the nodes you're connecting actually exist in your graph.
• Unidirectional vs Bidirectional Edges: If you're working with an undirected graph (most common for shortest path problems), you have to add edges in both directions.
• Uninitialized Adjacency Pointers: Forgetting to set adjacent to nullptr in your Node constructor can lead to wild pointer errors when adding edges.

Robust add_edge Implementation #

First, we'll need a helper function to find nodes by their label (since your graph is a linked list of Nodes):

// Helper to find a node by its label in the linked list of nodes
Node* findNode(Node* nodeListHead, char targetLabel) {
    Node* current = nodeListHead;
    while (current != nullptr) {
        if (current->label == targetLabel) {
            return current;
        }
        current = current->next;
    }
    return nullptr; // Node not found
}

// Function to add an edge between two nodes with a given weight
void addEdge(Node* nodeListHead, char fromLabel, char toLabel, int weight) {
    // Locate the two nodes we want to connect
    Node* fromNode = findNode(nodeListHead, fromLabel);
    Node* toNode = findNode(nodeListHead, toLabel);

    // Handle invalid nodes (critical to avoid crashes)
    if (fromNode == nullptr || toNode == nullptr) {
        cerr << "Error: Could not find one or both nodes (" << fromLabel << ", " << toLabel << ")!" << endl;
        return;
    }

    // Add edge from 'fromNode' to 'toNode'
    ListNode* newForwardEdge = new ListNode(toNode, weight);
    // Insert at the head of the adjacency list (easy to implement)
    newForwardEdge->next = fromNode->adjacent;
    fromNode->adjacent = newForwardEdge;

    // If this is an undirected graph, add the reverse edge too!
    // Omit this line if you're working with a directed graph
    ListNode* newReverseEdge = new ListNode(fromNode, weight);
    newReverseEdge->next = toNode->adjacent;
    toNode->adjacent = newReverseEdge;
}

Don't Forget Node Initialization #

Make sure your Node constructor properly initializes all pointers and values—especially the adjacent pointer to avoid wild pointers:

class Node {
public:
    int visited, distance;
    char label;
    Node* prev;
    Node* next;
    ListNode* adjacent;

    // Constructor with proper initialization
    Node(char lab) : 
        visited(0), 
        distance(INT_MAX), 
        label(lab), 
        prev(nullptr), 
        next(nullptr), 
        adjacent(nullptr) {}
};

Test to Verify Weight Initialization #

Here's a quick test to confirm edges and weights are being added correctly:

int main() {
    // Build a simple linked list of nodes
    Node* graphHead = new Node('A');
    graphHead->next = new Node('B');
    graphHead->next->next = new Node('C');

    // Add some edges with weights
    addEdge(graphHead, 'A', 'B', 5);
    addEdge(graphHead, 'A', 'C', 10);
    addEdge(graphHead, 'B', 'C', 3);

    // Print adjacency lists to check weights
    Node* currentNode = graphHead;
    while (currentNode != nullptr) {
        cout << "Node " << currentNode->label << " adjacent edges:\n";
        ListNode* currentEdge = currentNode->adjacent;
        while (currentEdge != nullptr) {
            cout << "  -> " << currentEdge->neighbor->label << " (Weight: " << currentEdge->weight << ")\n";
            currentEdge = currentEdge->next;
        }
        currentNode = currentNode->next;
    }

    // Don't forget to free memory in a real program!
    // (Omitted here for brevity)
    return 0;
}

Troubleshooting Tips #

• If your program crashes: Check if findNode is returning nullptr (invalid labels) or if adjacent was left uninitialized.
• If weights aren't showing up correctly: Double-check the ListNode constructor to ensure weight is being assigned properly.
• If edges are missing: Confirm you're adding reverse edges for undirected graphs, or that you're targeting the correct node labels.

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