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

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

이 도구는 무방향 그래프에서 최단 경로를 찾는 데 특화되어 있습니다. 최대 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: 그래프가 연결되지 않으면 어떤 결과가 나오나요?

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