온라인 그래프 이론 분석 도구

그래프 이론 분석 도구의 주요 기능

이 도구는 무방향 그래프에서 최단 경로를 찾는 데 특화되어 있습니다. 최대 500개의 고유 노드와 1000개의 간선을 지원하며, 음수 가중치는 허용되지 않습니다.

구체적인 예시

다음 간선을 입력했다고 가정합니다:

A,B,2
B,C,3
A,C,10

시작 노드를 A, 끝 노드를 C로 지정하면, 도구는 최단 거리 5와 경로 A → B → C를 반환합니다. 이는 A에서 C로 직접 가는 것보다 B를 경유하는 것이 더 짧기 때문입니다.

처리 방식

도구는 다익스트라 알고리즘을 사용합니다. 따라서 음수 가중치 간선이 있으면 오류가 발생하며, 0 가중치는 허용됩니다. 간선은 무방향으로 처리되며, 중복 간선 입력도 허용됩니다.

제한 사항

• 방향 그래프는 지원하지 않습니다.
• 좌표 시각화, 중심성 계산, 최소 신장 트리, 음수 간선 알고리즘은 제공하지 않습니다.
• 동일한 최단 경로가 여러 개인 경우 하나만 표시합니다.
• 연결 성분 계산은 제공하지 않습니다.

체크리스트

• 간선 형식이 올바른지 확인하세요 (쉼표로 구분).
• 시작/끝 노드가 간선 목록에 있는지 확인하세요.
• 가중치가 음수가 아닌지 확인하세요.
• 노드 수가 500개 이하인지 확인하세요.
• 결과의 경로가 예상과 일치하는지 검토하세요.

자주 묻는 질문

Q1: 가중치를 생략하면 어떻게 되나요?

가중치를 생략하면 기본값 1로 간주됩니다. 예를 들어 A,B는 A,B,1과 동일하게 처리됩니다.

Q2: 음수 가중치를 입력하면 어떻게 되나요?

다익스트라 알고리즘은 음수 가중치를 처리할 수 없으므로, 음수 가중치가 포함된 간선이 있으면 오류 메시지가 표시됩니다. 0 가중치는 허용됩니다.

Q3: 그래프가 연결되지 않으면 어떤 결과가 나오나요?

시작 노드에서 끝 노드로 가는 경로가 없으면 '연결되지 않음' 메시지가 표시됩니다. 이 경우 최단 거리나 경로는 제공되지 않습니다.

필드는 ASCII 쉼표로 구분하고 가중치 소수점은 점을 쓰세요. A,B는 가중치 1이지만 A,B,의 빈 가중치는 현재 0으로 읽으므로 값을 명시하세요. 빈 줄은 무시합니다. 이름은 대소문자를 구분하고 앞뒤 공백만 제거하며 쉼표를 포함할 수 없습니다. 시작과 끝이 같으면 거리는 0이고 경로는 해당 노드입니다. 노드 수는 목록 전체를 셉니다. 부동소수점 합에는 반올림 오차가 있을 수 있으며, 도달 가능한 거리라도 유한 범위를 넘으면 숫자 범위 오류가 발생합니다.